[LeetCode][Medium] 19. Remove Nth Node From End of List

Leetcode 網址: https://leetcode.com/problems/remove-nth-node-from-end-of-list/

題目說明:

給定一個 linked list 與整數 n，請刪除"倒數"第 n 個 node。 

Follow up: 能否在只跑一個 for loop 的情況下達成呢?

解題說明:

原本不太清楚 for loop 的定義所以直接用 stack 去解，

解完後去參考答案發現出題者想要的是用 two pointer 來解決問題，

其解法概念大致如下:

利用 first pointer 先跑 n 次 (first pointer = first pointer -> next)，

那這樣跑過 n 次後的 first pointer 只要再跑 size - n 次即可到 null，

因此我們可以用 first pointer 跑到 null 的同時更新 second pointer，

那麼 second pointer 屆時會指到要被刪除的 node，

不過這樣會有一個問題是，我們這樣會無法找到要被刪除的 node 之前一個，

因此這題的核心是需要搭配一個 dummy head，

藉由這個 dummy head 可以讓 second pointer 指向要被刪除的 node 之前一個，

此外這樣也能順帶完美解決刪除 head 的罕見情況 XD。

程式碼

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0, head);
        ListNode* firstNode = dummyHead, * secondNode = dummyHead;
        for (int i = 0; i < n + 1; i++) firstNode = firstNode->next;
        while (firstNode != NULL) {
            firstNode = firstNode->next;
            secondNode = secondNode->next;
        }
        secondNode->next = secondNode->next->next;
        return dummyHead->next;
    }
};

結果

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Remove Nth Node From End of List.

Memory Usage: 10.5 MB, less than 95.43% of C++ online submissions for Remove Nth Node From End of List.