19. Remove Nth Node From End of List - Medium

前往題目

想法

• 第一個想法是從頭到尾看有幾個，然後maintain一個集合，紀錄順序，但這樣會需要O(n)空間複雜，但時間也是O(n)
• 還是先從頭到尾看幾個，然後一個新的linkedlist是反向連接的，這樣反過來要找的時候就可以直接找了，因為原始的linkedlist是正向的，但是這樣空間也是O(n)吧，好像不管如何就是需要O(n)
• 對了，還要remove，然後回傳原始的head

思路

重點:

• 使用offset
• 使用two pointers

1. 右指針先和左指針拉開距離n
2. 因為最後是要刪除，所以是刪除node前一個node要接上他下下個node，因此這邊還需要在最前面加上一個dummy node，讓左指針從dummy node開始
3. 當右指針指到null的時候就代表左指針指向的node是要刪除的node的上一個node

Code

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // Extra node before head
        ListNode dummy = new ListNode(0, head);

        ListNode left = dummy;
        ListNode right = head;

        // Move the right pointer to the correct pos.
        // Creating offset
        while (n > 0 && right != null) {
            right = right.next;
            n--;
        }

        // Start the algorithm
        while (right != null) {
            left = left.next;
            right = right.next;
        }

        // Delete the specific node
        left.next = left.next.next;

        return dummy.next;
    }
}

2024/04/23

• 這題再回來看有變簡單，關鍵點是offset，可以理解為右指針比左指針走快了幾步，所以他就會比左指針早到幾步，那就是從終點數來的n了