19. Remove Nth Node From End of List

發表於 | 分類於

problem

solution

  • 因為只允許遍歷一遍 one pass，利用快慢指標
  • two pointer 不知道串列長度 iterative

先將快指標向右移動 n 個單位
慢指標與快指標一起向右移動，直到快指標到達串列尾部，慢指標的下一個節點則為要移除的節點，slow->next = slow->next->next; 移除掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *slow = new ListNode(-1), *fast = slow, *ret = slow;
        slow->next = head;
        while(n){
            fast = fast->next;
            n--;
        }
        while(fast->next){
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        return ret->next;
    }
};
  • recursive
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    ListNode *helper(ListNode* node, int n , int &cur)
    {
        if(!node){
            cur = 0;
            return nullptr;
        }
        node->next = helper(node->next, n, cur);
        if(++cur == n){
            return node->next;
        }
        return node;
    }
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int cur = -1;
        return helper(head, n, cur);
    }
};

analysis

  • time complexity O(n)
  • space complexity O(1)