iT邦幫忙

DAY 12
0

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

[Day12] 30 天挑戰演算法 - 從已排序的 list 中刪除有重複值的節點

題目來源Remove Duplicates from Sorted List

問題:
給予一個已排序過的 Linked List, 請試著刪除所有重複值的節點,使之所有節點的數值都只有出現過一次。

// 題目給的節點定義為
// Definition for singly-linked list.
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

例子
假設 Linked List 為 1->2->2, 則要回傳 1->2
假設 Linked List 為 1->1->2->3->3, 則要回傳 1->2->3

想法
因為這個是單向的 Linked List, 所以在處理這種情況時,我們所要做的就是把 目前節點 和 下一個節點 給保留下來。假設目前節點叫做 node, 下一個節點叫做 nextNode, 接著每一次判斷只要去比較 node.val 跟 nextNode.val 是否相等,如果不相等,就往再往下比。如果遇到相等的情況,只要把 node.next 指向 nextNode.next 所指向的節點就可以了。

不過,我相信用文字描述可能還是會有一點模糊,下面我就用圖示來表達,可能會更清楚一些。
如下圖,目前的 node 與 nextNode 的 val 相等(數值為2的節點有重複):

因為 nextNode 重複了 ,所以我們要將 node 的 next 指向 nextNode 的 next 所指向的節點(也就是 val 等於 3 的那個節點)。從另一個角度來說,也可以說是 刪除 nextNode 的意思,請見下圖:

從上圖可以很清楚看到,原本的 node 的 next 指向 val 也是 2 的節點,現在我們把 node 的 next 指向 nextNode 的 next 所指的節點,雖然目前的 nextNode 的 next 也是指向同一個點,但那無所謂,因為已經沒有任何節點指向目前的 nextNode 了,也可以看成目前的 nextNode 已經變刪除的意思,如下圖所示:

這時候,我們就可以繼續往下比對,也就是 node 指向 node 的 next 之後再讓 nextNode 指向 node 的 next 所指向的節點,之後再重複之前的比對動作直到最後一個節點。

// 刪除重複的節點 C# 版本
public removeDuplicate(ListNode head) {
 ListNode node = head;
 ListNode nextNode = null;

 while (node != null) {
  nextNode = node.next;
  
  if (nextNode == null) // 沒有下一個節點了, 也就是已經走訪到最後了
   node = null;
  else if (node.val == nextNode.val) // 若發現重複節點
   node.next = nextNode.next; // 跳過此重複節點,直接指向下一個節點(也就是刪除的意思)
  else
   node = node.next; // 繼續往下一個節點查看
  }
 return head;
}

上一篇
[Day11] 30天挑戰演算法 - 發糖果
下一篇
[Day13] 30 天挑戰演算法 - 二元樹的最大深度
系列文
連續30天,挑戰演算法30

尚未有邦友留言

立即登入留言