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

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

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

提示：

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

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

你能嘗試使用一趟掃描實現(xiàn)嗎？

具體實現(xiàn)

要刪除鏈表的倒數(shù)第 n 個節(jié)點，并返回鏈表的頭節(jié)點，我們可以使用一趟掃描的方法來實現(xiàn)。這個方法涉及使用兩個指針：快指針和慢指針。快指針先向前移動 n 步，然后慢指針從鏈表的頭節(jié)點開始，與快指針同時移動。當快指針到達鏈表的末尾時，慢指針所在的下一個節(jié)點就是倒數(shù)第 n 個節(jié)點。

以下是使用 Java 實現(xiàn)的刪除鏈表倒數(shù)第 n 個節(jié)點的函數(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)建一個啞節(jié)點，它的下一個節(jié)點是頭節(jié)點
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;


        // 快指針先走 n 步
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }


        // 快慢指針同時移動，直到快指針指向鏈表的末尾
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }


        // 慢指針的下一個節(jié)點就是倒數(shù)第 n 個節(jié)點，刪除它
        slow.next = slow.next.next;


        return dummy.next; // 返回啞節(jié)點的下一個節(jié)點，即新的頭節(jié)點
    }
}

使用示例：

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 哥的這個實現(xiàn)中，使用了一個啞節(jié)點來簡化邊界條件的處理，這樣即使要刪除的是頭節(jié)點，代碼也能正常工作。這個方法只需要一趟掃描，因此時間復(fù)雜度是 O(sz)，其中 sz 是鏈表的長度。

實現(xiàn)過程和步驟如下

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

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

這個方法的核心思想是利用快慢指針的差距來找到倒數(shù)第 n 個節(jié)點?？熘羔樝茸?n 步，然后快慢指針一起移動，直到快指針到達鏈表末尾。此時，慢指針所在的位置就是倒數(shù)第 n 個節(jié)點的前一個節(jié)點，這樣就可以很容易地刪除倒數(shù)第 n 個節(jié)點。

小結(jié)

V哥經(jīng)過測試，坐實了這個方法只需要一趟掃描，所以時間復(fù)雜度是 O(sz)，其中 sz 是鏈表的長度?？臻g復(fù)雜度是 O(1)，因為只需要常數(shù)級別的額外空間來存儲快慢指針和啞節(jié)點。