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

题目

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

进阶：

你能尝试使用一趟扫描实现吗？

解答

思路

一般来说，如果会删除头节点的话，我们创建一个哨兵节点 dummy 是比较合适的。最简单的做法：

• 遍历一遍，求出链表长度 sz，那么倒数第 n 个节点就是正数第 sz + 1 - n 个节点
• 再遍历一遍，删除第 sz + 1 - n 个节点即可

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        sz = 0
        dummy = ListNode(next=head)

        while head:
            head = head.next
            sz += 1
        
        cur = dummy

        for _ in range(sz - n):
            cur = cur.next
        
        cur.next = cur.next.next
        return dummy.next

那么能否一次遍历呢？

• 初始化右指针 right = dummy，右指针向右走 n 步
• 初始化左指针 left = dummy，此时左右指针之间距离相差 n
• 右指针走到倒数第 1 个节点时，左指针走到倒数第 n + 1 个节点
• 做删除操作

复杂度：

• 时间复杂度为 $O(n)$
• 空间复杂度为 $O(1)$

代码

Python 代码

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        
        right = dummy
        for _ in range(n):
            right = right.next
        
        left = dummy
        while right.next:
            left = left.next
            right = right.next
        
        left.next = left.next.next
        return dummy.next