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

成都創(chuàng)新互聯(lián)成立以來不斷整合自身及行業(yè)資源、不斷突破觀念以使企業(yè)策略得到完善和成熟，建立了一套“以技術(shù)為基點，以客戶需求中心、市場為導(dǎo)向”的快速反應(yīng)體系。對公司的主營項目，如中高端企業(yè)網(wǎng)站企劃 / 設(shè)計、行業(yè) / 企業(yè)門戶設(shè)計推廣、行業(yè)門戶平臺運營、成都app軟件開發(fā)公司、移動網(wǎng)站建設(shè)、微信網(wǎng)站制作、軟件開發(fā)、雅安服務(wù)器托管等實行標(biāo)準(zhǔn)化操作，讓客戶可以直觀的預(yù)知到從成都創(chuàng)新互聯(lián)可以獲得的服務(wù)效果。

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

刪除鏈表的倒數(shù)第 N 個結(jié)點

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

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

解題思路

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

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

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

思路一

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

思路二

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

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

舉栗

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

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

增加虛擬頭節(jié)點

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

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

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

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

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

網(wǎng)站欄目：動圖：刪除鏈表的倒數(shù)第N個結(jié)點
文章轉(zhuǎn)載：http://uogjgqi.cn/article/dphejhc.html