跳转至

19. 删除链表的倒数第N个节点

题目

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

示例 1:

输入：head = [1,2,3,4,5], n = 2

输出：[1,2,3,5]

示例 2:

输入：head = [1], n = 1

输出：[]

思路

双指针+虚拟头结点

要找到倒数第 n 个点，可以使用两个指针 slow 和 fast， 同时对链表进行遍历，并且 fast 比 slow 超前 n 个节点。当 fast 遍历到链表的末尾时，slow 就恰好处于倒数第 n 个节点。

题解

Go
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Val: 0, Next: head}
    slow, fast := dummy, dummy

    // 先走 n 步
    for ; n > 0; n-- {
        fast = fast.Next
    }
    fast = fast.Next

    for fast != nil {
        slow = slow.Next
        fast = fast.Next
    }

    slow.Next = slow.Next.Next
    return dummy.Next
}
Python
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        slow = fast = dummy = ListNode(next=head)
        for _ in range(n):
            fast = fast.next # fast指针先向右走 n 步
        while fast.next:
            slow = slow.next
            fast = fast.next # slow和fast指针一起走
        slow.next = slow.next.next # slow慢指针的下一个节点就是倒数第 n 个节点
        return dummy.next

复杂度

  • 时间复杂度：\(O(n)\)，\(n\) 为链表的长度。
  • 空间复杂度：\(O(1)\)

参考