19. Remove Nth Node From End of List

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics: Linked List、Two Pointers

一、題目

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:
remove_ex1

  • Input: head = [1,2,3,4,5], n = 2
  • Output: [1,2,3,5]

Example 2:

  • Input: head = [1], n = 1
  • Output: []

Example 3:

  • Input: head = [1,2], n = 1
  • Output: [1]

Constraints:

  • The number of nodes in the list is sz.
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

二、分析

  • 這是經典的鏈表問題，可以先遍歷一遍求得鏈表長度後，再去要刪去的節點從頭數是第幾個節點，接著找到該節點的前一個節點，再刪去該節點。
  • 更聰明的方法是使用前後指針，利用前指針先前進 n 步後，前後指針同時往前等速移動，後指針到達鏈表尾時，前指針正好指向從鏈表尾部數倒數第 n 個節點。

三、解題

1. Straight Forward

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(1)\)
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummy = new ListNode(-1, head);
    int len = 0;
    ListNode* curr = head;
    while (curr) {                      // 先求鏈表長度
        len++;
        curr = curr->next;
    }
    len -= n;                           // 求欲刪除的節點往頭算是第幾個節點
    curr = dummy;
    while (len--) curr = curr->next;    // 移動至該節點前
    curr->next = curr->next->next;      // 移除節點
    return dummy->next;
}

2. Two Pointers

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(1)\)
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummy = new ListNode(-1, head);
    ListNode* fast = dummy, *slow = dummy;
    while (n--) fast = fast->next;      // 前指針先走 n 步
    while (fast->next) {                // 前後指針等速移動至前指針走完
        fast = fast->next;
        slow = slow->next;
    }
    slow->next = slow->next->next;      // 移除節點
    return dummy->next;
}

回目錄 Catalog