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

题目

卡哥思路

卡哥是用双指针来解题，我没想出来这个思路。

精华部分：

双指针的经典应用，如果要到达倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾（nullptr）。slow所指向的节点就是倒数第n个节点。

跟着卡哥代码敲了下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode *fast = dummyHead;
        ListNode *slow = dummyHead;
        while (n-- && fast != nullptr)
        {
            fast = fast->next;
        }
        fast = fast->next;
        while (fast != nullptr)
        {
            slow = slow->next;
            fast = fast->next;
        }
        ListNode *tmp = slow->next;
        slow->next = tmp->next;
        delete tmp;
        ListNode *result = dummyHead->next;
        delete dummyHead;
        return result;
    }
};

不过卡哥的视频讲解部分认为这样写更好，更安全。（即让n先加一，而不是后面再做一步fast = fast->next;，这样做规避了n很大导致在做fast = fast->next;时fast已经为nullptr的风险）

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummyHead = new ListNode(0);
        dummyHead->next = head;
        ++n;
        ListNode *slow = dummyHead;
        ListNode *fast = dummyHead;
        while (n-- && fast != nullptr)
            fast = fast->next;
        while (fast != nullptr)
        {
            slow = slow->next;
            fast = fast->next;
        }
        ListNode *tmp = slow->next;
        slow->next = slow->next->next;
        delete tmp;
        return dummyHead->next;
    }
};