0%
Loading ...

【Leetcode 筆記】19. Remove Nth Node From End of List

題目解釋

給定 linked list 的 head,
從 linked list 的末端刪除第 n 個 node,並回傳其 head。

範例

  • 輸入: head = [1, 2, 3, 4, 5], n = 2
  • 輸出: [1, 2, 3, 5]

將 linked list 倒數第 2 個元素刪掉並 return head

最佳解法

很直覺的,可以拆分為三個步驟。

  1. 找到 n th 的 node
  2. n - 1th 的 next 直接改指到 n + 1th 的 node
  3. 快樂 return head

那麼,要怎麼找到 n th 的 node 呢?
又來到了我們的 快慢指針法(Fast-slow Pointers) 出場的時間。

忘記這是什麼或是想溫故知新的朋友,
可以參考 【Leetcode 筆記】143. Reorder List 窩 ~

一個概念各自表述:快慢指針法(Fast-slow Pointers)

之前的所使用到的快慢指針法,
是在一個迴圈裡面同時讓 slowfast 前進不同步數,
從而讓 slow 到達 linked list 的中間,fast 則先到達末端。

這題的小技巧就在於,我們其實可以先挪動 fast 指針 n 格,
再讓 slowfast 走到直到 fast 觸底的地方。

假設我們 linked list 的長度是 lfast 觸底時是第 l 個元素,
slow 則會在 l - n 的位置,
slow.next 就會是倒數第 n 個元素 (可以嘗試帶數字進去就知道了)。

程式碼

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        slow, fast = dummy, dummy

        # let fast move n steps first
        for _ in range(n):
            fast = fast.next

        # let fast move to the linked list end
        while fast.next:
            slow = slow.next
            fast = fast.next

        # slow.next is the <n>th node !
        # <n - 1>th.next -> <n + 1>th node
        #   (slow.next) -> (slow.next.next)
        slow.next = slow.next.next

        return dummy.next

時間複雜度

O(n),n 是 linked list 的元素個數。

空間複雜度

O(1),沒有多存東西。

結語

感覺 linked list 相關的題目很多都會要令個 dummy node 保平安呢 ~

數據女巫 𝔻.𝕡𝕪𝕤 🔮

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

The reCAPTCHA verification period has expired. Please reload the page.