串列應用題 移除尾巴數來的第n個節點 Leetcode #19

這題的題目在這裡:

題目敘述

題目會給定我們一個串列，和一個n值，要求我們刪除尾巴數來的第n個節點。

例如
1->2->3->4->5 和 給定n值=2，要求我們刪除尾巴數來的第2個節點。

尾巴數來的第2個節點是4，刪除之後，更新連結，輸出答案如下

1->2->3->5

測試範例

Example 1:

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]

演算法:

使用雙指針演算法，一個快指針，一個慢指針。

快指針提早領先出發n步，接著慢指針和快指針再一起往前移動。
當快指針抵達終點時，慢指針會剛好指向尾巴數來第n個節點的前一個位置。

註:
為什麼要尾巴數來第n個節點前一個位置?
因為不僅僅是刪除而已，還要更新連結 node.next

程式碼

class Solution:
　def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
　　
　　# use dummy head will make the removal of head node easier
　　dummy_head = ListNode(-1)
　　dummy_head.next = head
　　
　　# cur keeps iteration till the end
　　# prev_of_removal traverses to the previous node of the one of being removed
　　cur, prev_of_removal = dummy_head, dummy_head
　　
　　
　　while cur.next != None:
　　　
　　　# n-step delay for prev_of_removal
　　　if n <= 0:
　　　　prev_of_removal = prev_of_removal.next
　　　　
　　　cur = cur.next
　　　
　　　n -=1
　　
　　
　　# Remove the N-th node from end of list
　　n_th_node = prev_of_removal.next
　　prev_of_removal.next = n_th_node.next
　　
　　del n_th_node
　　
　　return dummy_head.next

複雜度分析

時間複雜度: O( n )
從左到右，把整個串列掃描一遍。

空間複雜度: O( 1 )
用到一組雙指針，指針所占用的空間大小都是固定的，為常數級別O(1)。

關鍵知識點

在於畫圖觀察規律，想到用快、慢雙指針，快指針領先慢指針n步，定位尾巴數來第n個節點的演算法。

Reference:

[1] Python/Go/JS/C++ O(n) by two-pointers [w/ Visualization] - Remove Nth Node From End of List - LeetCode