runtime 0 ms, beats 100% of cpp submissions
O(n) solution with explanation

tags: linked list, pointer

Remove Nth Node From End of List

📖 description

給定一個 linked list ，刪掉倒數第 k 個點

🧠 solution

為了解決這個問題，我們可以先遍歷一次 list ，再根據每個節點標記編號，但實際上，這題可以用一個非常精美的方式解決，空間複雜度為 O(1) 。

這個技巧就是 slow pointer and fast pointer ，我們維護一個 nextn_ptr 走在 next_ptr 的前 k 步，而如果 nextn_ptr 走到底了， next_ptr 就會是我們需要刪除的倒數第 k 個點。

⏳ time complexity

遍歷一次，時間複雜度 O(n)
總時間複雜度 O(n)

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* next_ptr = head;
        ListNode* nextn_ptr = head;
        while(n-- && nextn_ptr!=nullptr){
            nextn_ptr = nextn_ptr->next;   // 走在前 k 步
        }
        if(nextn_ptr==nullptr){
            return head->next;             // 如果 list 不夠長就刪除頭
        }
        while(nextn_ptr->next!=nullptr){   // 讓 nextn_ptr 走到底
            next_ptr = next_ptr->next;
            nextn_ptr = nextn_ptr->next;
        }
        if(next_ptr->next == nullptr){
            return nullptr;
        }
        auto tmp = next_ptr->next;
        next_ptr->next = next_ptr->next->next;
        delete tmp;                        // 刪除點
        return head;
    }
};