Linked list系列 Leetcode 題

141、160、206、21

這邊是分門別類的刷題筆記區
本篇的主題是 linked list data structures
超簡介可以參考我之前文章
尋找本主題相關的題目主要參考Cyc2018大大的文章

然後菜鳥如我寫題暫時都以easy為主
所以沒特別註明的題目難度都是 easy

因為我主要使用的語言是javaScript
linked list 是平常比較少用到的資料結構，不太熟所以刻意整理起來練習
另外爬文看到有人覺得瞭解這個資料結構對於 stack 跟 queues也有幫助，所以先整理這部分

在解linked list題之前，
我先思考到的是”如何使用js實作出一個linked list”這個問題
因為js沒有內建這種資料結構必須要自己手動做出來
先收集了一些網路資訊:
1. 用 JavaScript 實作單向連結串列（Singly Linked List）
2. [LeetCode] 用JavaScript實作Linked List (這篇有把linked list長相範例寫出來比較好想像)

要自己寫出來有各種功能的還是挺麻煩的(而且題目應該不會用到)
(後來還是有寫了，有興趣的話請看我的gitHub: Linked List)
直接先用題目附上的ListNode() constructor function

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 * this.val = (val===undefined ? 0 : val)
 * this.next = (next===undefined ? null : next)
 * }
 */

這篇筆記目標是記錄leetcode相關解題的部分

141. Linked List Cycle

題目
提示有ListNode的constructor function
建立好.val 跟 .next 兩個 property 可以使用

two pointers / Floyd’s Cycle Detection Algorithm

討論區看到的解法
概念是:
做兩個指標一快(fast)一慢(head)，如果有loop的話，快的總有一天會被慢的追上，追得上就代表有loop
(註: 寫到後來發現這應該是龜兔賽跑演算法，詳情請見下面題.234)

while迴圈確認 fast && fast.next → 如果有到尾巴(.next = null)就會結束迴圈
如果有loop就會待在圈內，中間就是追逐戰
head一次走一步，fast一次走兩步
追上(相等)的時候 return true

const hasCycle = (head) => {
 let fast = head;
 while (fast && fast.next) {
 head = head.next;
 fast = fast.next.next;
 if (head === fast) return true;
 }
 return false;
};

Runtime: 83 ms (只要有cycle)終有一天追到妳

set

討論區看到的解法

轉個資料結構改用 set去檢查有沒有重複的內容
沒有的話就加進去，跑到完為止
中間發現已經有加過的東西的話表示有loop

var hasCycle = function(head) {
 
 let x = new Set() // use a set to store each node 
 while(head){ 
 if(x.has(head)){ return true }
  x.add(head) 
  head=head.next 
 }
 return false
};

Runtime: 129 ms

用迴圈然後建一個新的hashSet所以應該是
T: O(n) S:O(n)

看到有類似的解法不用set用array接，除了語法有點差別
覺得其他好像沒有什麼差別就先不記錄了

160. Intersection of Two Linked Lists

題目

題目example 1的圖示

跟上一題一樣有建立好.val 跟 .next 兩個 property 可以使用

two pointers

討論區看到的解法
作者還有畫圖解釋很可愛
簡單來說:
把兩條接起來，A跟B條來舉例的話:
A → AB
B → BA

如果有相交，第二次交會同時讀到，以上面的example1來舉例

A: a1-a1-c1-c2-c3
B: b1-b2-b3-c1-c2-c3

→接起來
AB: a1-a2-c1-c2-c3-b1-b2-b3-c1-c2-c3
BA: b1-b2-b3-c1-c2-c3-a1-a2-c1-c2-c3

______
while迴圈用and ，兩個都要達到:

1. p不等於q: 找到相交點就跳出
2. 後面條件( )裡面先判斷用or : 只有兩個都false的時候會回傳 false → 也就是"p跟q同時跑完，p.next跟q.next 同時都沒有了的狀況" 才會得到 false
   只有其中一條先跑完(長短不一)的時候會被接上另一條繼續跑

var getIntersectionNode = function(headA, headB) {
 let p = headA;
 let q = headB;
 
 while(p!=q && ( p.next || q.next)){
 if(p.next == null) p = headB;
 else p=p.next;
 if(q.next == null) q= headA;
 else q=q.next;
 }

 if(p==q) return p;
};

Runtime:150 ms

T: O(n+m)
S: O(1)

Hashset

討論區看到的解法

看到題目的第一個直覺反應是用set，兩個set有聯集的話就代表有結合
然後再把第一個點找出來
結果找到用set更好的解法:
建立一個set 然後兩條輪流丟
while迴圈放or → 兩個都丟完了才結束
只要set裡面已經有重複的，第一個重複的表示交集點直接 return
兩條都丟完沒有就null

var getIntersectionNode = function(headA, headB) {
    const set = new Set();
    while(headA || headB) {
        if(headA) {
            if(set.has(headA)) {
                return headA;
            }
            else {
                set.add(headA);
            }
            headA = headA.next;
        }
        if(headB) {
            if(set.has(headB)) {
                return headB;
            }
            else {
                set.add(headB);
            }
            headB = headB.next;
        }
    }
    return null;
};

Runtime: 164 ms

206. Reverse Linked List

題目
一樣有建立好.val 跟 .next 兩個 property 可以使用

two pointers

(但我其實用了三個變數接XD)
就是前方pointer一邊往前落後pointer改指的方向
用直敘句寫出來

reverseList = function(head)
 prev = null
 curr = head
 nextOne = null
while(curr !== null){
        nextOne = curr.next
        curr.next = prev
        
        prev = curr
        curr = nextOne
    }
    return prev

• Time: O(n)
• Space: O(1)

後來看到有人用ES6解構賦值的語法寫，更簡潔了

var reverseList = function(head) {
    let [prev, current] = [null, head]
    while(current) {
        [current.next, prev, current] = [prev, current, current.next]
    }
    return prev
}

用解構賦值的寫法當沒有對應的值時，就會得到undefined (所以讀到最後一個時候就會跳出迴圈)
然後看起來 + 網路爬文看起來起賦值好像是'同時'沒有順序干擾的
但我實測順序還是要照邏輯寫，譬如說:
[curr.next, prev, curr] = [prev, curr, curr.next] (O)
[curr, prev, curr.next] = [curr.next, curr, prev](X)

p.s. 而且 [ ] 運算子應該是左->右相依性的吧
也可以參考討論區解答底下有前輩的說明這部分:

JS engine takes a snapshot of the values on the right side. 
This means, the values referred by [prev, current, current.next] at the time of assignment get saved. Those saved values from the snapshot then get assigned to [current.next, prev, current] sequentially.

(想像) js引擎對右邊的值拍了一個快照，然後依序把快照中的值存到左邊

然後翻了一下似乎沒有看到什麼其他的解法就先這樣

21. Merge Two Sorted Lists

題目

Brute Force

這題要回傳merge好的一條linklist，
所以使用題目附上的constructor function “ ListNode( ) “
new 新的 "mergehead" instance

然後進入迴圈，跑到其中一條跑完為止
開始比誰val小，meg指向比較小的那個
被指過的就移向
一條跑完之後就會跳出迴圈，剩下的直接全部接起來
最後return的時候要記得從第一層的next turn (head的頭使用預設0不在輸入的兩條之內)

var mergeTwoLists = function(l1, l2) {
 let mergehead = new ListNode()
 let meg = mergehead
  while(l1 && l2){
   if(l1.val > l2.val){
    meg.next = l2
    l2 = l2.next
   } else {
    meg.next = l1
    l1 = l1.next
   }
  meg = meg.next
 }
 meg.next = l1?l1:l2
 return mergehead.next
};

使用了迴圈
T: O(n)

然後討論區看到有不少人用遞迴的方式寫比較漂亮

var mergeTwoLists = function(l1, l2) {
  if(!l1 || !l2) return (l1? l1:l2);
  if(l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
  }
};

參考: Linked list Javascript實作及Leet code題目解析