題目:
Given the head of a linked list, remove the nth node from the end of the list and return its head.
給定head一個鍊錶，從列表末尾刪除節點並返回其頭
題目重點
給定一個單向鏈表，刪除「倒數第 n 個節點」。
返回新的鏈表頭節點。
需要處理刪除頭節點的情況。
思路分析
方法一：兩次遍歷
第一次遍歷計算鏈表長度 len。
第二次遍歷，找到 第 (len-n) 個節點，把它的下一個節點刪除。
缺點：需要遍歷兩次鏈表，時間複雜度 O(2n)。
方法二：快慢指針（最佳解）
虛擬頭節點：建立一個 dummy node 指向 head，避免刪除頭節點時要特判。
快指針先走 n+1 步：讓快指針和慢指針保持距離 n。
快慢指針一起走：直到快指針到達鏈表尾部，此時慢指針剛好停在「待刪除節點的前一個節點」。
刪除節點：slow.next = slow.next.next。
iThome鐵人賽
看影片追技術