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

2024-12-18 13:53 更新

大家好,我是 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é)點開始,與快指針同時移動。當(dāng)快指針到達(dá)鏈表的末尾時,慢指針?biāo)诘南乱粋€節(jié)點就是倒數(shù)第 n 個節(jié)點。

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

  1. class ListNode {
  2. int val;
  3. ListNode next;
  4. ListNode(int x) { val = x; }
  5. }
  6. public class Solution {
  7. public ListNode removeNthFromEnd(ListNode head, int n) {
  8. ListNode dummy = new ListNode(0); // 創(chuàng)建一個啞節(jié)點,它的下一個節(jié)點是頭節(jié)點
  9. dummy.next = head;
  10. ListNode fast = dummy;
  11. ListNode slow = dummy;
  12. // 快指針先走 n 步
  13. for (int i = 0; i < n; i++) {
  14. fast = fast.next;
  15. }
  16. // 快慢指針同時移動,直到快指針指向鏈表的末尾
  17. while (fast.next != null) {
  18. fast = fast.next;
  19. slow = slow.next;
  20. }
  21. // 慢指針的下一個節(jié)點就是倒數(shù)第 n 個節(jié)點,刪除它
  22. slow.next = slow.next.next;
  23. return dummy.next; // 返回啞節(jié)點的下一個節(jié)點,即新的頭節(jié)點
  24. }
  25. }

使用示例:

  1. public class Main {
  2. public static void main(String[] args) {
  3. // 示例 1
  4. ListNode head1 = new ListNode(1);
  5. head1.next = new ListNode(2);
  6. head1.next.next = new ListNode(3);
  7. head1.next.next.next = new ListNode(4);
  8. head1.next.next.next.next = new ListNode(5);
  9. int n1 = 2;
  10. ListNode newHead1 = new Solution().removeNthFromEnd(head1, n1);
  11. printList(newHead1); // 應(yīng)該輸出 [1,2,3,5]
  12. // 示例 2
  13. ListNode head2 = new ListNode(1);
  14. int n2 = 1;
  15. ListNode newHead2 = new Solution().removeNthFromEnd(head2, n2);
  16. printList(newHead2); // 應(yīng)該輸出 []
  17. // 示例 3
  18. ListNode head3 = new ListNode(1);
  19. head3.next = new ListNode(2);
  20. int n3 = 1;
  21. ListNode newHead3 = new Solution().removeNthFromEnd(head3, n3);
  22. printList(newHead3); // 應(yīng)該輸出 [1]
  23. }
  24. private static void printList(ListNode head) {
  25. while (head != null) {
  26. System.out.print(head.val + " ");
  27. head = head.next;
  28. }
  29. System.out.println();
  30. }
  31. }

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

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

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

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

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

小結(jié)

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

以上內(nèi)容是否對您有幫助:
在線筆記
App下載
App下載

掃描二維碼

下載編程獅App

公眾號
微信公眾號

編程獅公眾號