鏈表刪除倒數(shù)第N個(gè)節(jié)點(diǎn)：一趟掃描的最優(yōu)解法

大家好，我是 V 哥，有這樣一道面試題如下：

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

提示：

鏈表中結(jié)點(diǎn)的數(shù)目為 sz

● 1 <= sz <= 30 ● 0 <= Node.val <= 100 ● 1 <= n <= sz

你能?chē)L試使用一趟掃描實(shí)現(xiàn)嗎？

具體實(shí)現(xiàn)

要?jiǎng)h除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)，并返回鏈表的頭節(jié)點(diǎn)，我們可以使用一趟掃描的方法來(lái)實(shí)現(xiàn)。這個(gè)方法涉及使用兩個(gè)指針：快指針和慢指針?？熘羔樝认蚯耙苿?dòng) n 步，然后慢指針從鏈表的頭節(jié)點(diǎn)開(kāi)始，與快指針同時(shí)移動(dòng)。當(dāng)快指針到達(dá)鏈表的末尾時(shí)，慢指針?biāo)诘南乱粋€(gè)節(jié)點(diǎn)就是倒數(shù)第 n 個(gè)節(jié)點(diǎn)。

以下是使用 Java 實(shí)現(xiàn)的刪除鏈表倒數(shù)第 n 個(gè)節(jié)點(diǎn)的函數(shù)：

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0); // 創(chuàng)建一個(gè)啞節(jié)點(diǎn)，它的下一個(gè)節(jié)點(diǎn)是頭節(jié)點(diǎn)
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;
        // 快指針先走 n 步
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        // 快慢指針同時(shí)移動(dòng)，直到快指針指向鏈表的末尾
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // 慢指針的下一個(gè)節(jié)點(diǎn)就是倒數(shù)第 n 個(gè)節(jié)點(diǎn)，刪除它
        slow.next = slow.next.next;
        return dummy.next; // 返回啞節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，即新的頭節(jié)點(diǎn)
    }
}

使用示例：

public class Main {
    public static void main(String[] args) {
        // 示例 1
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(3);
        head1.next.next.next = new ListNode(4);
        head1.next.next.next.next = new ListNode(5);
        int n1 = 2;
        ListNode newHead1 = new Solution().removeNthFromEnd(head1, n1);
        printList(newHead1); // 應(yīng)該輸出 [1,2,3,5]
        // 示例 2
        ListNode head2 = new ListNode(1);
        int n2 = 1;
        ListNode newHead2 = new Solution().removeNthFromEnd(head2, n2);
        printList(newHead2); // 應(yīng)該輸出 []
        // 示例 3
        ListNode head3 = new ListNode(1);
        head3.next = new ListNode(2);
        int n3 = 1;
        ListNode newHead3 = new Solution().removeNthFromEnd(head3, n3);
        printList(newHead3); // 應(yīng)該輸出 [1]
    }
    private static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }
}

代碼輸出結(jié)果與題目中的示例輸出是一致， V 哥的這個(gè)實(shí)現(xiàn)中，使用了一個(gè)啞節(jié)點(diǎn)來(lái)簡(jiǎn)化邊界條件的處理，這樣即使要?jiǎng)h除的是頭節(jié)點(diǎn)，代碼也能正常工作。這個(gè)方法只需要一趟掃描，因此時(shí)間復(fù)雜度是 O(sz)，其中 sz 是鏈表的長(zhǎng)度。

實(shí)現(xiàn)過(guò)程和步驟如下

下面 V 哥把實(shí)現(xiàn)過(guò)程再詳細(xì)說(shuō)明一下，為了幫助你更好的理解代碼的邏輯實(shí)現(xiàn)：

1. 創(chuàng)建一個(gè)啞節(jié)點(diǎn)（dummy node），并將其設(shè)置為鏈表的頭節(jié)點(diǎn)之前的一個(gè)節(jié)點(diǎn)。啞節(jié)點(diǎn)的引入是為了簡(jiǎn)化邊界條件的處理，特別是當(dāng)需要?jiǎng)h除的節(jié)點(diǎn)是頭節(jié)點(diǎn)時(shí)。
2. 初始化兩個(gè)指針：快指針（fast）和慢指針（slow），它們都指向啞節(jié)點(diǎn)。
3. 快指針先向前移動(dòng) n 步。這樣，快指針和慢指針之間就保持了 n 個(gè)節(jié)點(diǎn)的距離。
4. 快指針和慢指針同時(shí)向前移動(dòng)，直到快指針到達(dá)鏈表的末尾（即快指針的下一個(gè)節(jié)點(diǎn)為 null）。此時(shí)，慢指針的位置就是倒數(shù)第 n 個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。
5. 修改慢指針的 next 指針，使其指向下一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，從而跳過(guò)倒數(shù)第 n 個(gè)節(jié)點(diǎn)，實(shí)現(xiàn)刪除操作。
6. 返回啞節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，即新的頭節(jié)點(diǎn)。

這個(gè)方法的核心思想是利用快慢指針的差距來(lái)找到倒數(shù)第 n 個(gè)節(jié)點(diǎn)。快指針先走 n 步，然后快慢指針一起移動(dòng)，直到快指針到達(dá)鏈表末尾。此時(shí)，慢指針?biāo)诘奈恢镁褪堑箶?shù)第 n 個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，這樣就可以很容易地刪除倒數(shù)第 n 個(gè)節(jié)點(diǎn)。

小結(jié)

V哥經(jīng)過(guò)測(cè)試，坐實(shí)了這個(gè)方法只需要一趟掃描，所以時(shí)間復(fù)雜度是 O(sz)，其中 sz 是鏈表的長(zhǎng)度?？臻g復(fù)雜度是 O(1)，因?yàn)橹恍枰?shù)級(jí)別的額外空間來(lái)存儲(chǔ)快慢指針和啞節(jié)點(diǎn)。