AI毛毛的blog

leetcode打卡-0019删除链表的倒数第N个结点

题目描述

给你一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。

解题思路

1. 快慢指针

单链表的遍历方向只能从头到尾单向遍历，如果要删除倒数第N个节点，就意味着后面还有N-1步才能遍历到末尾。

所以考虑用快慢指针的方法，快指针先走N-1步，然后两个指针再同时前进，这样当快指针走到末尾时，慢指针正好指向倒数第N个节点。

不过为了便于删除节点，当慢指针指向倒数第N+1个节点时就停下来即可，所以，先让快指针走N步。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        fast = head
        slow = head

        # 快指针先走N步
        for _ in range(n):
            fast = fast.next

        # 如果快指针走完了整个链表，那么链表长度为N，倒数第N个即头节点
        if fast is None:
            return head.next

        while fast.next:
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next

        return head
  • 时间复杂度: O(n)，其中n是链表的长度
  • 空间复杂度: O(1)

总结

单链表由于其方向上的一致性，运用双指针解法时候一般优先考虑快慢指针。