[[416447]]

本文轉載自微信公眾號「三分鐘學前端」，作者sisterAn。轉載本文請聯系三分鐘學前端公眾號。

給定一個鏈表，刪除鏈表的倒數第 n 個節點，并且返回鏈表的頭結點。

示例：

給定一個鏈表: 1->2->3->4->5, 和 n = 2. 
當刪除了倒數第二個節點后，鏈表變為 1->2->3->5. 

說明：

給定的 n 保證是有效的。

進階：

你能嘗試使用一趟掃描實現嗎?

解法：快慢指針

解題思路： 需要刪除鏈表中的倒數第 n 個節點，我們需要知道的就是倒數第 n+1 個節點，然后刪除刪除倒數第 n+1 節點的后繼節點即可

步驟：

使用 2 個指針：

• fast 快指針提前走 n+1 步
• slow 指針指向當前距離 fast 倒數第 n 個節點， 初始為 head

然后， fast 、 slow 同步向前走，直到 fast.next 為 null

此時，fast 為最后一個節點，slow 就是倒數第 n+1 個節點，此時問題就變更為刪除鏈表中的 slow 的后繼節點

但存在一個問題，當鏈表長度為 n 時，fast 是前進不到 n+1 個節點位置的，所以此時有兩種解決思路：

• 創建一個頭節點 preHead ，設置 preHead.next = head ，這樣就可以解決以上問題，刪除倒數第 n 個節點后，返回的 preHead.next 即可
• 另外一種是，fast 快指針提前走 n 步后，判斷 fast.next 是否為 null ，即 fast 是否是最后一個節點，如果是，則 head 為倒數第 n 個節點，此時問題可以簡化為刪除頭節點;如果不是， fast = fast.next ，fast 再前進一步，slow 為倒數第 n+1 個節點，也解決了以上問題。

解決方案一：添加 preHead 節點

const removeNthFromEnd = function(head, n) { 
    let preHead = new ListNode(0) 
    preHead.next = head 
    let fast = preHead, slow = preHead 
    // 快先走 n+1 步 
    while(n--) { 
        fast = fast.next 
    } 
    // fast、slow 一起前進 
    while(fast && fast.next) { 
        fast = fast.next 
        slow = slow.next 
    } 
    slow.next = slow.next.next 
    return preHead.next 
}; 

解決方案二：單獨處理倒數第 n 節點

const removeNthFromEnd = function(head, n) { 
    let fast = head, slow = head 
    // 快先走 n 步 
    while(--n) { 
        fast = fast.next 
    } 
    if(!fast.next) return head.next 
    fast = fast.next 
    // fast、slow 一起前進 
    while(fast && fast.next) { 
        fast = fast.next 
        slow = slow.next 
    } 
    slow.next = slow.next.next 
    return head 
}; 

時間復雜度：O(n)

空間復雜度：O(1)

來源：https://github.com/sisterAn/JavaScript-Algorithms