題目： LeetCode - 19. Remove Nth Node From End of List

題目說明

給一個 List 和一個整數 n，要求刪除 List 的倒數第 n 個 node。

解題思路

若想刪除倒數第 n 個 node，就需要倒數第 n + 1 個 node，可以使用兩個指針，先使兩個指針相隔 n + 1 個 node，之後兩者都往前走，直到前面的指針走到尾巴，此時後面的指針恰好為倒數第 n + 1 個 node，此時作串接及刪除的動作即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n)
    {
        ListNode dummy(0, head);
        auto first = head, second = &dummy;
        for(int i = 0; i < n; ++i) first = first->next;
        while(first) first = first->next, second = second->next;
        auto tmp = second->next;
        second->next = second->next->next;
        delete tmp;
        return dummy.next;
    }
};