[[393057]]

本文轉載自微信公眾號「程序員小熊」，作者Dine。轉載本文請聯系程序員小熊公眾號。   

本文主要介紹一道面試中常考鏈表刪除相關的題目，即 leetcode 19. 刪除鏈表的倒數第 N 個結點。采用 雙指針 + 動圖 的方式進行剖析，供大家參考，希望對大家有所幫助。

刪除鏈表的倒數第 N 個結點

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

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

解題思路

在鏈表中要刪除某個節點 nodeB，必須先找到 nodeB 的前一節點 nodeA ，再將 nodeA 指向 nodeB 的下一節點 nodeC ，從而實現節點 nodeB 的刪除。

例如要刪除鏈表 L(1->2->3->4->5) 中 值為 3 的節點，首先得找到該節點的前一節點(值為 2 的節點)，才能實現該節點的刪除，如下圖示：

題目要求刪除 倒數第 n 個 節點，所以首先得找到 該節點的前一節點 ，但由于不知道 整個鏈表的長度，因此不知道 待刪除的節點是正數的第幾個節點，所以很難從頭節點開始遍歷時刪除掉這個節點。

思路一

先遍歷一遍鏈表，獲取整個鏈表的長度;假設整個鏈表的長度為 l，則可知要刪除的節點為第 l - n + 1 個節點;再遍歷一遍，刪除倒數第 n 個節點。例如鏈表 L 為 1->2->3->4->5，n = 3，則要刪除的節點為 第 5 - 3 + 1 = 3 個節點 。

思路二

盡管思路一可行，但是需要 遍歷鏈表兩遍，不夠簡潔，而且題目的 進階 中也提到嘗試使用一趟掃描實現，因此本文采用 雙指針 的策略，實現通過一次掃描刪除 倒數第 n 個節點 。

在上一期鏈表相關專題 虛擬頭節點秒殺鏈表問題 中提到 增加虛擬頭節點 的策略解決鏈表問題，增加虛擬頭節點的 好處 在于：不需要單獨考慮頭節點，這樣對頭節點的處理就像跟其它節點一樣。本文也同樣采用這種策略。

舉栗

以鏈表 1->2->3->4->5，n = 3 為栗，如下如示。

按照上面分析，先要找到 倒數第 3 個節點的前一節點，即值為 2 的節點;

增加虛擬頭節點

值為 2 的節點是 倒數第 4 個節點(后往前數)，增加兩指針 fast/slow，分別指向最后一個元素(NULL)和上圖中 target 的位置;

此時 fast 跟 slow 之間的間距是固定(n = 3)的，找到 target(slow)后，只需要刪除其下一節點即可，但 slow 指向的節點前面有多少個節點該如何確定呢?

由于當前已知 fast 和 slow 指向節點之間的長度是固定的，只需要將這兩個指針向前挪，直到 slow 挪到虛擬頭節點(值為 0)的位置，此時 fast 指向值為 4 的節點的位置，fast 只需要由虛擬頭節點的位置 右移 n + 1 = 4 即可。如下圖示：

當 fast 右移至值為 4 的節點時，指針 slow 和 fast 同時右移，直至 fast 移到 NULL，此時 slow 剛好到 target 位置，即指向 倒數第 n + 1 個節點，如下圖示。

Show me the Code

c++

ListNode* removeNthFromEnd(ListNode* head, int n) { 
    ListNode* dummyHead = new ListNode(0); 
    dummyHead->next = head; 
    ListNode *slow = dummyHead, *fast = dummyHead; 
    for (int i = 0; i < n + 1; ++i) { 
        fast = fast->next; 
    } 
 
    while (fast != NULL) { 
        slow = slow->next; 
        fast = fast->next; 
    } 
 
    ListNode* delNode = slow->next; 
    slow->next = delNode->next; 
    delete delNode; 
 
    ListNode* retNode = dummyHead->next; 
    delete dummyHead; 
 
    return retNode; 
} 

java

ListNode removeNthFromEnd(ListNode head, int n) { 
    ListNode dummyHead = new ListNode(0); 
    dummyHead.next = head; 
    ListNode slow = dummyHead, fast = dummyHead; 
    for (int i = 0; i < n + 1; ++i) { 
        fast = fast.next; 
    } 
 
    while (fast != null) { 
        slow = slow.next; 
        fast = fast.next; 
    } 
 
    slow.next = slow.next.next; 
    return dummyHead.next; 
}