【LeetCode 】19. 删除链表的倒数第N个节点（双指针法 + 逐行注释）

1. 题目描述

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

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

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

2. 解题思路

2.1 方法一：两次遍历算法

思路

该问题可以简化：删除从列表开头数起的第 (L - n + 1) 个结点，其中 L 是列表的长度。只要我们找到列表的长度 L，这个问题就很容易解决。

算法

首先我们将添加一个 哑结点（哨兵节点）作为辅助，该结点位于列表头部。哑结点用来简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部。
第一次遍历，我们找出列表的长度 L。
第二次遍历，找到要删除的节点，即第 (L - n) 个结点，删除即可。

但是题目要求一次遍历。

2.2 方法二：一次遍历算法

设置前后两个指针，front 和 back，他们之间的间隔是固定的，保持为 n，而后同步往后移动。当 back 指针指向尾结点之后的 None 时，front 节点刚好指向需要删除节点的前一个节点，而后删除即可。详见下面动画。（动画中 p 即 front，q即 back）
参考：动画图解 LeetCode 第 19 号问题：删除链表的倒数第 N 个节点.

2.3 Python代码详解

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        s = ListNode(None)  # 增加哨兵节点，便于统一对头结点操作 （删除头结点比较方便）
        s.next = head  

        front = s           # 前后两个指针，当 back 指针指向 尾结点之后的 None 时，front 节点刚好指向需要删除节点的前一个节点 
        back = s
        for k in range(0, n+1):  # 移动 back 指针，使得 front 和back 指针间隔 n 个节点的距离
            back = back.next

        # print(front, back) # 善于使用 print 进行调试 
        
        while (back):            # 两个指针同步后移
            front = front.next
            back = back.next
        
        front.next = front.next.next   # 删除节点操作
        print(front)
        return s.next       # 不能返回 head 因为可能头结点都删除掉了！！！