[[393057]]

本文轉(zhuǎn)載自微信公眾號(hào)「程序員小熊」，作者Dine。轉(zhuǎn)載本文請(qǐng)聯(lián)系程序員小熊公眾號(hào)。   

本文主要介紹一道面試中常考鏈表刪除相關(guān)的題目，即 leetcode 19. 刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)。采用 雙指針 + 動(dòng)圖 的方式進(jìn)行剖析，供大家參考，希望對(duì)大家有所幫助。

刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)

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

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

解題思路

在鏈表中要?jiǎng)h除某個(gè)節(jié)點(diǎn) nodeB，必須先找到 nodeB 的前一節(jié)點(diǎn) nodeA ，再將 nodeA 指向 nodeB 的下一節(jié)點(diǎn) nodeC ，從而實(shí)現(xiàn)節(jié)點(diǎn) nodeB 的刪除。

例如要?jiǎng)h除鏈表 L(1->2->3->4->5) 中 值為 3 的節(jié)點(diǎn)，首先得找到該節(jié)點(diǎn)的前一節(jié)點(diǎn)(值為 2 的節(jié)點(diǎn))，才能實(shí)現(xiàn)該節(jié)點(diǎn)的刪除，如下圖示：

題目要求刪除 倒數(shù)第 n 個(gè) 節(jié)點(diǎn)，所以首先得找到 該節(jié)點(diǎn)的前一節(jié)點(diǎn) ，但由于不知道 整個(gè)鏈表的長(zhǎng)度，因此不知道 待刪除的節(jié)點(diǎn)是正數(shù)的第幾個(gè)節(jié)點(diǎn)，所以很難從頭節(jié)點(diǎn)開(kāi)始遍歷時(shí)刪除掉這個(gè)節(jié)點(diǎn)。

思路一

先遍歷一遍鏈表，獲取整個(gè)鏈表的長(zhǎng)度;假設(shè)整個(gè)鏈表的長(zhǎng)度為 l，則可知要?jiǎng)h除的節(jié)點(diǎn)為第 l - n + 1 個(gè)節(jié)點(diǎn);再遍歷一遍，刪除倒數(shù)第 n 個(gè)節(jié)點(diǎn)。例如鏈表 L 為 1->2->3->4->5，n = 3，則要?jiǎng)h除的節(jié)點(diǎn)為 第 5 - 3 + 1 = 3 個(gè)節(jié)點(diǎn) 。

思路二

盡管思路一可行，但是需要 遍歷鏈表兩遍，不夠簡(jiǎn)潔，而且題目的 進(jìn)階 中也提到嘗試使用一趟掃描實(shí)現(xiàn)，因此本文采用 雙指針 的策略，實(shí)現(xiàn)通過(guò)一次掃描刪除 倒數(shù)第 n 個(gè)節(jié)點(diǎn) 。

在上一期鏈表相關(guān)專題 虛擬頭節(jié)點(diǎn)秒殺鏈表問(wèn)題 中提到 增加虛擬頭節(jié)點(diǎn) 的策略解決鏈表問(wèn)題，增加虛擬頭節(jié)點(diǎn)的 好處 在于：不需要單獨(dú)考慮頭節(jié)點(diǎn)，這樣對(duì)頭節(jié)點(diǎn)的處理就像跟其它節(jié)點(diǎn)一樣。本文也同樣采用這種策略。

舉栗

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

按照上面分析，先要找到 倒數(shù)第 3 個(gè)節(jié)點(diǎn)的前一節(jié)點(diǎn)，即值為 2 的節(jié)點(diǎn);

增加虛擬頭節(jié)點(diǎn)

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

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

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

當(dāng) fast 右移至值為 4 的節(jié)點(diǎn)時(shí)，指針 slow 和 fast 同時(shí)右移，直至 fast 移到 NULL，此時(shí) slow 剛好到 target 位置，即指向 倒數(shù)第 n + 1 個(gè)節(jié)點(diǎn)，如下圖示。

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; 
}