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

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

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

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

image

image

解題思路

在鏈表中要?jiǎng)h除某個(gè)節(jié)點(diǎn) nodeB，必須先找到 該節(jié)點(diǎn)的前一節(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)的刪除，如下圖示：

image

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

思路一

先遍歷一遍鏈表，獲取整個(gè)鏈表的長度；假設(shè)整個(gè)鏈表的長度為 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) 。

思路二

盡管思路一可行，但是需要 遍歷鏈表兩遍，不夠簡潔，而且題目的 進(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 為栗，如下如示。

image

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

image

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

image

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

image

此時(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)之間的長度是固定的，只需要將這兩個(gè)指針向前挪，直到 slow 挪到虛擬頭節(jié)點(diǎn)（值為 0）的位置，此時(shí) fast 指向值為 4 的節(jié)點(diǎn)的位置，fast 只需要由虛擬頭節(jié)點(diǎn)的位置 右移 n + 1 = 4 即可。如下圖示：

image

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

image

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

更多精彩，關(guān)注公眾號(hào)【程序員小熊】