LeetCode 題解 | 19. 刪除鏈表的倒數第N個節點

08-24

來自專欄領扣（LeetCode）5 人贊了文章

題目描述：

給定一個鏈表，刪除鏈表的倒數第 n 個節點，並且返回鏈表的頭結點。

示例：

給定一個鏈表: 1->2->3->4->5, 和 n = 2.當刪除了倒數第二個節點後，鏈表變為 1->2->3->5。

說明：

給定的 n 保證是有效的。

進階：

你能嘗試使用一趟掃描實現嗎？

刪除鏈表的倒數第N個節點 - 領扣 (LeetCode)?

leetcode-cn.com

摘要：

本文適用於初學者。它介紹了以下內容：鏈表的遍歷和刪除其末尾的第 n 個元素。

方法一、兩次遍歷演算法：

思路

我們注意到這個問題可以容易地簡化成另一個問題：刪除從列表開頭數起的第 $(L?n+1)$ 個結點，其中 $L$ 是列表的長度。只要我們找到列表的長度 $L$ ，這個問題就很容易解決。

演算法

首先我們將添加一個啞結點作為輔助，該結點位於列表頭部。啞結點用來簡化某些極端情況，例如列表中只含有一個結點，或需要刪除列表的頭部。在第一次遍歷中，我們找出列表的長度 $L$ 。然後設置一個指向啞結點的指針，並移動它遍歷列表，直至它到達第 $(L?n)$ 個結點那裡。我們把第 $(L?n)$ 個結點的 next 指針重新鏈接至第 $(L?n+2)$ 個結點，完成這個演算法。

圖 1. 刪除列表中的第 L - n + 1 個元素

Java 代碼實現

public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0); dummy.next = head; int length = 0; ListNode first = head; while (first != null) { length++; first = first.next; } length -= n; first = dummy; while (length > 0) { length--; first = first.next; } first.next = first.next.next; return dummy.next;}

複雜度分析

時間複雜度： $O(L)$ ，
該演算法對列表進行了兩次遍歷，首先計算了列表的長度 $L$ 其次找到第 $(L?n)$ 個結點。操作執行了 $2L?n$ 步，時間複雜度為 $O(L)$ 。
空間複雜度： $O(1)$ ，
我們只用了常量級的額外空間。

方法二、一次遍歷演算法：

演算法

上述演算法可以優化為只使用一次遍歷。我們可以使用兩個指針而不是一個指針。第一個指針從列表的開頭向前移動 $n+1$ 步，而第二個指針將從列表的開頭出發。現在，這兩個指針被 $n$ 個結點分開。我們通過同時移動兩個指針向前來保持這個恆定的間隔，直到第一個指針到達最後一個結點。此時第二個指針將指向從最後一個結點數起的第 $n$ 個結點。我們重新鏈接第二個指針所引用的結點的 next 指針指向該結點的下下個結點。

圖 2. 刪除鏈表的倒數第 n 個元素

Java 代碼實現

public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode first = dummy; ListNode second = dummy; // Advances first pointer so that the gap between first and second is n nodes apart for (int i = 1; i <= n + 1; i++) { first = first.next; } // Move first to the end, maintaining the gap while (first != null) { first = first.next; second = second.next; } second.next = second.next.next; return dummy.next;}

複雜度分析

時間複雜度： $O(L)$ ，
該演算法對含有 $L$ 個結點的列表進行了一次遍歷。因此時間複雜度為 $O(L)$ 。
空間複雜度： $O(1)$ ，
我們只用了常量級的額外空間。