iT邦幫忙

2021 iThome 鐵人賽

DAY 15
2
Software Development

30天用JavaScript刷題刷起來!系列 第 15

Day 15:Remove Duplicates from linked list

這題開始之前先來介紹一下Linked list(連結串列)的資料結構。

Linked list(連結串列)使用node(節點)來記錄、表示、儲存資料(data),並利用每個node中的pointer指向下一個node,來將多個node串起來。並以null 來代表Linked list的終點。

Node的結構如題目定義:


  function ListNode(val, next) {
      this.val = (val===undefined ? 0 : val)
      this.next = (next===undefined ? null : next)
  }

今天題目的目標是要把Linked list中node的數字重複者都移除掉,並回傳移除後的結果,且題目有說這個Linked list是已經由小到大排序好的了,回傳時也要是排序好的。

這題相較簡單是因為題目給我們的Linked list是已經排序過的,今天如果沒有排序過我們就需要用到之前提過的hashTable來儲存已經拜訪過的值,遇到重複的數再來調整pointer。

回到今天的題目。同理上面描述的這種方式當然可以套用在我們今天的題目,不過沒有必要,因為我們的Linked list是已經排序過的,我們可以省掉額外儲存的hashtable

以範例來說

Input: head = [1,1,2,3,3]
Output: [1,2,3]

目前Linked list的形狀如下

1 → 1 → 2 → 3 → 3 → null

當我們今天一開始在1的時候

我們用一個temp來儲存1的下一個數,也就是tmp = 1 (1.next = 1)

因為1 === 1

我們需要把第二個1拔掉

需要做以下的操作

current = head
// 把1的下下一個數(2)存到tmp
tmp = current.next.next
// 把1的下一個數換成tmp
current.next = tmp   

也就是說,我們只要一個loop,把這個Linked list走過,遇到next和現在一樣,我們就仿造以上做法。如果有多個重複,我們可以利用while來實作,直到下個不同的node才去調整pointer

整體時間複雜度為:O(n),空間複雜度為:O(1)

var deleteDuplicates = function (head) {
  let current = head;
  while (current !== null) {
    let nextDifferent = current.next;
    while (nextDifferent !== null && nextDifferent.val === current.val) {
      nextDifferent = nextDifferent.next;
    }
    current.next = nextDifferent;
    current = nextDifferent
  }
  return head;
};

看完上述的做法,不要忘記做做看如果Input Linked list沒有sort的情況喔!
/images/emoticon/emoticon08.gif

明日題目預告:挑戰一下 Remove Nth Node From End of List(Medium)


上一篇
Day 14:凱撒密碼之Shifting Letters
下一篇
Day 16 : Remove Nth Node From End of List
系列文
30天用JavaScript刷題刷起來!30

1 則留言

1
ycchiuuuu
iT邦新手 5 級 ‧ 2021-09-30 12:42:53

我乖乖來思考 Linked list 沒有 sort 的情況,猜想應該是下面兩種方式:

  1. 犧牲時間複雜度,先排序,再按照文章中的方式跑
  2. 犧牲空間複雜度,建立一個 lookup table 供查詢,使用 Map 去紀錄有出現過的數字,出現一次就變成 true,出現兩次看到是 true 就把 node 移除,這樣依然是跑一次迴圈即可

(邊吃飯邊思考,沒有打成 code XD

Jen iT邦新手 5 級 ‧ 2021-09-30 13:35:37 檢舉

都是正解/images/emoticon/emoticon12.gif

我要留言

立即登入留言