iT邦幫忙

DAY 26
0

連續30天,挑戰演算法系列 第 26

[Day26] 30 天挑戰演算法 - 從List的尾巴刪除第N個節點

題目來源:Remove Nth Node From End of List

問題:
給予一個 Linked List, 試著刪除從尾巴算來第 N 個節點,並回傳 head

假設給予的 Linked List = 1->2->3->4->5, 並且 N = 2
再移除從尾巴算來第N個節點之後,這個 Linked List 會變成 1-->2->3->5

並且,題目給的 N 永遠都是有效的。
請嘗試在第一輪跑還就可以刪除並回傳結果。

想法:
這題目指定要從一個 Linked List 後面數來第 N 個節點,但又希望在第一輪(也就是每個節點只能訪問過一次)就要夠完成此任務。所以最簡單的方是就是另外宣告一個具有 index 的 ArrayList 來暫存,就可以在每個節點都訪問過一次後,直接針對該 index 去刪除。但如此一來的缺點就是要額外宣告記憶體空間使用才能完成。如果我們想要空間複雜度為 O(1) 的話,勢必不能這麼做。這時候我們可以利用多個指標來達成目的,就可以不用額外在宣告記憶體空間來暫存節點了。

如果要用指標來標記我們欲刪除的節點,我們就必須要知道指標應該要指在那邊,所以可以先考慮一下三個狀況:

  1. 如果要刪除的節點是 第一個節點
  2. 如果要刪除的節點是最 後一個節點
  3. 如果要刪除的節點是 非頭也非尾 的節點

如果要刪除的節點是倒數最後一個節點,也就是第一個節點,那麼我們就必須要有一個假的節點來指向第一個節點。
dummyNode -> firstNode -> secondNode -> ... -> null
這時要刪除倒數最後一個節點的執行方是就是
dummyNode.next = firstNode.next
所以我們會需要有一個節點指向 firstNode, 而另一個節點指向 dummyNode。

如果我們要刪除的節點是倒數第一個節點,假設輸入的 Linked List 如下:
dummyNode -> firstNode -> secondNode -> ...(N-1)thNode -> NthNode -> null
這時要刪除倒數第一個節點的執行方式就是
(N-1)thNode.next = NthNode.next
所以我們同樣需要一個節點指向 (N-1)thNode , 另一個節點指向 NthNode。

不過問題來了,如果是倒數第一個節點,我可以利用 node.next == null,那如果是倒數最後一個節點呢?所以我們還需要一個節點來判斷是否已經到了最後一個節點了。

綜合以上判斷,我們需要的節點指標應該要有

  1. deleteNode (指向要被刪除的節點)
  2. dummyNode (指向 head 節點)
  3. seekNode (最終要指向最後一個節點)
  4. preDeleteNode (指向要被刪除的前一個節點)

那這三個指標節點的關係應該如何呢?以下用三張圖來觀察一下:

  1. 假設 N = 5, 則這三個指標節的關係如下

  2. 假設 N = 1, 則這三個指標節點關係如下

  3. 假設 N = 3, 則這三個指標節點關係如下

從上面三張圖可以很清楚知道,preDeleteNode 一定會在 deleteNode 前面,seekNode 一定會指向最後一個節點。而 deleteNode 剛好是會指向倒數N個節點的位置。並且訪問節點的終止條件為 seekNode.next == null

java 主要的流程

while( seekNode.next != null ) {
    index += 1;
    seekNode = seekNode.next;
    if (index >= n)
        deleteNode = deleteNode.next;
    if (index >= n+1)
        preDeleteNode = preDeleteNode.next;
}

當 seekNode 訪問到最後一個節點時,這時候我們就可以把 deleteNode 給刪除了,並回傳 dummyNode 所指向的 LinkList 了。

preDeleteNode.next = deleteNode.next;
return dummyNode.next;

java 完整解答

public static ListNode remveFromEndNode(ListNode head, int n) {
    if (head == null)
        return null;
    
    ListNode dummyNode = new ListNode(0);
    dummyNode.next = head;
    
    ListNode deleteNode = dummyNode;
    ListNode preDeleteNode = dummyNode;
    ListNode seekNode = dummyNode;
    int index = 0;
        
    while(seekNode.next != null) {
        index += 1;
        
        seekNode = seekNode.next;
        if (index >= n)
            deleteNode = deleteNode.next;
        if (index >= n+1)
            preDeleteNode = preDeleteNode.next;
    }
        
    preDeleteNode.next = deleteNode.next;
    return dummyNode.next;
}

上一篇
[Day25] 30 天挑戰演算法 - 最長的共同字首(prefix)
下一篇
[Day27] 30 天挑戰演算法 - 最後一個單字長度
系列文
連續30天,挑戰演算法30

尚未有邦友留言

立即登入留言