[[416447]]

本文轉(zhuǎn)載自微信公眾號(hào)「三分鐘學(xué)前端」，作者sisterAn。轉(zhuǎn)載本文請(qǐng)聯(lián)系三分鐘學(xué)前端公眾號(hào)。

給定一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。

示例：

給定一個(gè)鏈表: 1->2->3->4->5, 和 n = 2. 
當(dāng)刪除了倒數(shù)第二個(gè)節(jié)點(diǎn)后，鏈表變?yōu)?nbsp;1->2->3->5. 

說明：

給定的 n 保證是有效的。

進(jìn)階：

你能嘗試使用一趟掃描實(shí)現(xiàn)嗎?

解法：快慢指針

解題思路： 需要?jiǎng)h除鏈表中的倒數(shù)第 n 個(gè)節(jié)點(diǎn)，我們需要知道的就是倒數(shù)第 n+1 個(gè)節(jié)點(diǎn)，然后刪除刪除倒數(shù)第 n+1 節(jié)點(diǎn)的后繼節(jié)點(diǎn)即可

步驟：

使用 2 個(gè)指針：

• fast 快指針提前走 n+1 步
• slow 指針指向當(dāng)前距離 fast 倒數(shù)第 n 個(gè)節(jié)點(diǎn)， 初始為 head

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

此時(shí)，fast 為最后一個(gè)節(jié)點(diǎn)，slow 就是倒數(shù)第 n+1 個(gè)節(jié)點(diǎn)，此時(shí)問題就變更為刪除鏈表中的 slow 的后繼節(jié)點(diǎn)

但存在一個(gè)問題，當(dāng)鏈表長(zhǎng)度為 n 時(shí)，fast 是前進(jìn)不到 n+1 個(gè)節(jié)點(diǎn)位置的，所以此時(shí)有兩種解決思路：

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

解決方案一：添加 preHead 節(jié)點(diǎn)

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 一起前進(jìn) 
    while(fast && fast.next) { 
        fast = fast.next 
        slow = slow.next 
    } 
    slow.next = slow.next.next 
    return preHead.next 
}; 

解決方案二：?jiǎn)为?dú)處理倒數(shù)第 n 節(jié)點(diǎ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 一起前進(jìn) 
    while(fast && fast.next) { 
        fast = fast.next 
        slow = slow.next 
    } 
    slow.next = slow.next.next 
    return head 
}; 

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(1)

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