# LeetCode 解題筆記 (Linked List類型題目)

解題時要注意的重點
1. 一題多解，找不同的思維；可以看討論區的解題方法
2. 不要盲目刷題，至少要帶走一些想法
3. 精通一種解法；某些題型適合某一種演算法，可以做統整
4. 定義題目內容與輸出的結果；例如考官到底要什麼；題目給的例子是不是分類過的array

[影片來源](https://www.youtube.com/watch?v=NdWYxz3izH4)

## [難度Easy] 類型：Linked List
### 021. Merge Two Sorted Lists
[題目網址](https://leetcode.com/problems/merge-two-sorted-lists/)
> 將兩個Linked List 合併，而且順序要從小到大
> 範例：[1,2,2,3] + [1,3] = [1,1,2,2,3,3]

var mergeTwoLists = function(l1, l2) {
    // 儲存結果的ListNode
    var result = new ListNode(0);
    // 目前Node位置
    var c = result;

    while(l1 !== null && l2 !==null){
        // l1,l2較小的數加入result
        if(l1.val > l2.val){
            c.next = l2;
            l2 = l2.next;
        } else {
            c.next = l1;
            l1 = l1.next
        }
        c = c.next;
    }

    //將l1,l2剩下的Node加到result
    if(l1 !== null){
        c.next = l1;
    }

    if(l2 !== null){
        c.next = l2;
    }
    return result.next
};

1. 先建立一個Linked List，將要返回的內容串接在後面
2. 先比較兩個Linked List l1、l2 head的value大小，將較小的加入result(c.next = l1或l2)
3. 加入之後，將Linked List串接數減少一個(l1 = l1.next、l2 = l2.next)
4. 繼續串接下一個(c = c.next)，直到l1、l2其中一個沒有node可以串接(l1 !== null && l2 !==null)
5. 將剩下的list串接上去

[作法來源](https://skyyen999.gitbooks.io/-leetcode-with-javascript/content/questions/21md.html)
[同樣解法1](https://leetcode.com/problems/merge-two-sorted-lists/discuss/341711/Clean-Javascript)

var mergeTwoLists = function(l1, l2) {
    let res = new ListNode();
    let cur = res;
    while(l1 && l2){
        if(l1.val <= l2.val){
            cur.next = new ListNode(l1.val);
            l1 = l1.next;
            cur = cur.next;
        }
        else {
            cur.next = new ListNode(l2.val);
            l2 = l2.next;
            cur = cur.next;
        }
    }
    cur.next = l1 || l2;
    return res.next;
};

[同樣解法2，但比較簡潔](https://leetcode.com/problems/merge-two-sorted-lists/discuss/167585/javascript-clean-solution)

### 083. Remove Duplicates from Sorted List
[題目網址](https://leetcode.com/problems/remove-duplicates-from-sorted-list/)
> 給予1個個Linked List，移除重複的部分
> Input: 1->1->2->3->3；Output: 1->2->3

var deleteDuplicates = function (head) {
  if(!head || !head.next) return head
  let current = head
  while(current.next){
    if(current.val === current.next.val){
      current.next = current.next.next
    } else {
      current = current.next
    }
  }
  return head
};

1. 如果給予的List什麼都沒有，或只有一個node，那就直接回傳head
2. 接著開始串接，將初始值current設定為Head，當下一個值相同時，串接到下下一個node，不相同時，繼續下一個node，直到current.next為null為止
3. [參考來源](https://skyyen999.gitbooks.io/-leetcode-with-javascript/content/questions/83md.html)

var deleteDuplicates = function(head) {    
    if(!head) {
        return head;
    }
   var node = head.next;
   var prev = head;
   
   while (node) {
       if (node.val !== prev.val) {
           prev.next = node;
           prev = node;
       }
       node = node.next; 
   }
   prev.next = null;
   return head 
};

1. 如果給予的List什麼都沒有，或只有一個node，那就直接回傳head
2. 不停歷遍所有node(while(node)、node = node.next)，如果遇到值不同的，就更新next，與當下歷遍pre的位置[(參考來源)](https://leetcode.com/problems/remove-duplicates-from-sorted-list/discuss/28706/Javascript-Solution)

### 141. Linked List Cycle
[題目網址](https://leetcode.com/problems/linked-list-cycle/)
> 給予一個個Linked List，裡面的數值可能會重複，判斷這個list是不是一個循環的list；
> 關於怎樣循環，請見題目內的說明

var hasCycle = function (head) {
  let cur = head
  if(!cur || !cur.next) return false
  // key:value value:next value
  const obj = {}  
  while(cur.next){
    if (obj[cur.val] === cur.next.val) return true
    obj[cur.val] = cur.next.val
    cur = cur.next
  }
  return false
};

1. 先判斷有沒有list或是不是只有一個node，如果是的話，那就不能循環，回傳fale
2. 建立一個object，key紀錄current當下歷遍node的值，value則是下一個node的值
3. 開始歷遍node，每一次歷遍時，紀錄數值到object中，當發現貯存的key與value存在時，代表已經開始循環了，回傳true

var hasCycle = function(head) {
    if(head == null || head.next == null){
        return false; 
    }
    var node = head;
    while(node != null ){
        if(node.flag){
            return true;
        }    
        // 標記這個node已經跑過
        node.flag = true;   
        node = node.next;
    }
    return false;
}

每經過一個node就標記，如果有標記，代表已經開始循環了

var hasCycle = function(head) {
    if(head == null || head.next == null){
        return false; 
    }

    var slow = head.next;
    var fast = head.next.next;
    if(fast == null){
        return false;
    }

    while(slow != fast){
        if(fast.next == null){
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;

        if(slow == null || fast == null){
            return false;
        }
    }
    return true;
}

[快慢指針做法](https://skyyen999.gitbooks.io/-leetcode-with-javascript/content/questions/141md.html)

###### tags: `javascript` `LeetCode` `Linked List`