建站
咨詢
售后
建站咨詢
新聞中心
本文轉(zhuǎn)載自微信公眾號(hào)「程序員小熊」，作者Dine。轉(zhuǎn)載本文請(qǐng)聯(lián)系程序員小熊公眾號(hào)。
成都創(chuàng)新互聯(lián)成立以來(lái)不斷整合自身及行業(yè)資源、不斷突破觀念以使企業(yè)策略得到完善和成熟，建立了一套“以技術(shù)為基點(diǎn)，以客戶需求中心、市場(chǎng)為導(dǎo)向”的快速反應(yīng)體系。對(duì)公司的主營(yíng)項(xiàng)目，如中高端企業(yè)網(wǎng)站企劃 / 設(shè)計(jì)、行業(yè) / 企業(yè)門戶設(shè)計(jì)推廣、行業(yè)門戶平臺(tái)運(yùn)營(yíng)、成都app軟件開發(fā)公司、移動(dòng)網(wǎng)站建設(shè)、微信網(wǎng)站制作、軟件開發(fā)、雅安服務(wù)器托管等實(shí)行標(biāo)準(zhǔn)化操作，讓客戶可以直觀的預(yù)知到從成都創(chuàng)新互聯(lián)可以獲得的服務(wù)效果。
本文主要介紹一道面試中?？兼湵韯h除相關(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)開始遍歷時(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)通過一次掃描刪除 倒數(shù)第 n 個(gè)節(jié)點(diǎn) 。
在上一期鏈表相關(guān)專題 虛擬頭節(jié)點(diǎn)秒殺鏈表問題 中提到 增加虛擬頭節(jié)點(diǎ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;
- }
新聞標(biāo)題：動(dòng)圖：刪除鏈表的倒數(shù)第N個(gè)結(jié)點(diǎn)
當(dāng)前網(wǎng)址：http://m.5511xx.com/article/dphejhc.html
