19 - Remove Nth Node From End Of List

#medium
Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

/**
 * 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* slow = dummyHead;
        ListNode* fast = dummyHead;
        while(n-- && fast != NULL) {
            fast = fast->next;
        }
        fast = fast->next; // fast再提前走一步，因為需要讓slow指向刪除節點的上一個節點
        while (fast != NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next; 
        
        // ListNode *tmp = slow->next;  C++釋放內存的邏輯
        // slow->next = tmp->next;
        // delete nth;
        
        return dummyHead->next;
    }
};

思路

雙指針的經典應用，如果要刪除倒數第n個節點，讓fast移動n步，然後讓fast和slow同時移動，直到fast指向鏈表末尾。刪掉slow所指向的節點就可以了。

思路是這樣的，但要注意一些細節。

分為如下幾步：

• 首先這裡我推薦大家使用虛擬頭結點，這樣方便處理刪除實際頭結點的邏輯，如果虛擬頭結點不清楚，可以看這篇： 鏈表：聽說用虛擬頭節點會方便很多？
• 定義fast指針和slow指針，初始值為虛擬頭結點，如圖：

• fast首先走n + 1步 ，為什麼是n+1呢，因為只有這樣同時移動的時候slow才能指向刪除節點的上一個節點（方便做刪除操作），如圖：

• fast和slow同時移動，直到fast指向末尾，如題：

• 刪除slow指向的下一個節點，如圖：