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

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

class Solution {
public:
  ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode *Eager = head;
    ListNode *Lazy = head;

    // Eager first
    for (int i = 0; i < n; ++i)
      Eager = Eager->next;

    ListNode *Prev = nullptr;
    // Then both
    while (Eager) {
      Prev = Lazy;
      Lazy = Lazy->next;
      Eager = Eager->next;
    }

    if (!Prev)
      head = head->next;
    else
      Prev->next = Lazy->next;
    delete Lazy;

    return head;
  }
};

这题是前后双指针，不是快慢双指针，很有意思。

此外注意一下删除节点的写法。删除操作总是需要维护一个 Prev 的，我们可以通过判断它是否为空，来决定是否要把头节点后移。

二刷

说实话这个题目跟 142. 环形链表 II 有异曲同工之妙的，都是「你先走，我殿后」的情况，可以补充记忆。至于这道题的图示的话，大概是

$$ [_{L\to}^{E\to}\ 7\ 6\ [_L\ 5\ 4\ 3\ [^{E\to}\ 2\ 1\ [^E $$

类似于这种感觉吧。

class Solution {
public:
  ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode Dummy(0, head);
    ListNode *Eager = head, *Lazy = head, *Prev = &Dummy;
    while (n--)
      Eager = Eager->next;
    while (Eager) {
      Prev = Prev->next;
      Eager = Eager->next;
      Lazy = Lazy->next;
    }
    Prev->next = Lazy->next;
    delete Lazy;
    return Dummy.next;
  }
};

我这个其实叫三指针，其实压根用不着，因为你会发现 Lazy 其实就是 Prev->next，所以完全可以按照官解进行简化，让 Lazy 变得 Lazier：

class Solution {
public:
  ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode Dummy(0, head);
    ListNode *Eager = head, *Lazier = &Dummy;
    while (n--)
      Eager = Eager->next;
    while (Eager) {
      Eager = Eager->next;
      Lazier = Lazier->next;
    }
    ListNode *Delete = Lazier->next;
    Lazier->next = Delete->next;
    delete Delete;
    return Dummy.next;
  }
};

以后见到这个题就想着「卷狗（Eager）和懒狗（Lazier）」就行了。

三刷

class Solution {
public:
  ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode *Pred = head;
    ListNode PreFollow(0, head), *Follow = &PreFollow;
    for (int i = 0; i < n; ++i)
      Pred = Pred->next;
    while (Pred) {
      Pred = Pred->next;
      Follow = Follow->next;
    }
    ListNode *Delete = Follow->next;
    if (Delete == head)
      head = Follow->next->next;
    Follow->next = Follow->next->next;
    delete Delete;
    return head;
  }
};

我操，对啊，这个写法压根用不着，因为我们在用Follow进行遍历的过程当中已经天然地修改了PreFollow.next，所以只需要返回PreFollow.next就可以了，牛逼。