一个双指针小技巧——倒数第N个节点

一道题目

先来看leetcode的第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]

一般来说，我们会先遍历一遍链表，计算出链表的长度len，然后再遍历一遍，删除第len-n+1个节点。 但是这样需要遍历两遍链表，时间复杂度是O(2n)，能不能只遍历一遍呢？

双指针技巧

我们可以使用双指针技巧: 设置两个指针fast和slow，fast先走n步，然后slow和fast一起走，当fast走到链表末尾时，slow正好走到倒数第n个节点，如下所示：

例如{0,1,2,3,…,n}，找到倒数第k个节点

1. fast先走k步，fast指向第k+1个节点，slow指向节点0
   
2. fast和slow一起走，当fast走到末尾时，slow正好走到倒数第k个节点
   

0 -> 1 ...-> k -> ... -> n -> null
s            f                        
f和s相距k
0 -> 1 ...-> k -> ... -> n -> null
                   s            f 
f(null)和s相距k,s指向倒数第k个节点

但是，由于题目的链表是单向的，我们无法直接删除slow指向的节点，因为我们需要知道它的前一个节点才能删除它。此处笔者开始的想法是在head前面添加一个指针p3，这样就可以同时找到倒数第k个节点和它的前一个节点了。 代码实现如下：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
       ListNode* fast = head;
       ListNode* slow = head;
       ListNode* p3 = new ListNode(-1);
       p3 -> next = head;
       int cnt = 0;
       while (fast != nullptr) {
        fast = fast->next;
        cnt++;
        if (cnt > n) {
            slow = slow->next;
            p3 = p3->next;
        }
       }
       p3->next = slow->next;
       return head;
    }
};

但是这样还有一个问题，当k=n时，slow指向的是头节点，如果直接返回head,会导致头节点没有被删除。此时我们需要返回head->next，所以我们需要在代码中添加一个判断：

//处理删除首项
if (cnt == n) {
    return head->next;
}

最后的解法

这简直糟透了，使用哑节点本就是为了避免特殊情况

• 我们上面的问题在于return了head，在删除head的情况下出错。其实我们可以直接返回dummy->next，这样就不需要再判断cnt==n的情况了。
• 另一个优化是，我们也不需要p3指针了，直接用slow指针来找到倒数第n个节点的前一个节点即可。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* fast = head;
        ListNode* dummy = new ListNode(-1);
        dummy -> next = head;
        ListNode* slow = dummy; //slow从dummy开始
        int cnt = 0;
        while (fast != nullptr) {
            fast = fast->next;
            cnt++;
            if (cnt > n) {
                slow = slow->next;
            }
        }
        slow->next = slow->next->next; //删除倒数第n个节点
        return dummy->next; //直接返回dummy->next
    }
};

总结

通过双指针技巧，我们可以在一次遍历中找到并删除链表的倒数第n个节点，时间复杂度为O(n)，空间复杂度为O(1)。这种方法不仅高效，而且代码简洁，避免了多次遍历链表的麻烦。