一腳踏入軟體工程師寫 Code 的世界，不免俗地會碰上 Leetcode 的測驗，來測試你的溝通力、系統性地解決問題的能力和如何化抽象為具體。第四週的活動要進入較為難想像的 Linked List 為主。
![[筆記] AlphaCamp 不只是刷題的 Leetcode 訓練營 – 3](https://smlpoints.com/wp-content/uploads/notes-alphacamp-leetcode-training-camp-1.jpg "[筆記] AlphaCamp 不只是刷題的 Leetcode 訓練營 – 3")
課程相關資訊
[連結]：https://www.accupass.com/event/2010251353233453323900
課程對應章節：Week4 U29~U31
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
Linked List
1. Linked List 屬於較為高階的資料結構，所以多半是需要親自實作
2. 由 Node 組成，並具有指向性連到下一個 Node
3. 實務上，可以分為 Simple Linked List ( 單向 )、Doubly Linked List ( 雙向 )、Circular Linked List ( 環型 )
4. 和 Array 相比，它不需要連續的記憶體空間，資料插入和刪除很方便，但要查找就會辛苦一些
5. Tree 就如同非線性的 Linked List，延展性比起單線的 Linked List 佳
Linked List 邏輯
1. 反轉：在反轉前，要先記下原先的連結狀態，再將連結斷開。通常會搭配 While、遞迴等方法來實作。
2. 若使用遞迴方式解，會利用函式 Stack 的特性，快速將目標元素導引到倒數第二個，並將 cur.next.next 指向自己，將 cur.next 切斷。
LeetCode 題目
143. Reorder List
連結：https://leetcode.com/problems/reorder-list/
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
var reorderList = function(head) { if (!head || !head.next) return head // 分快慢指針，用來區分兩邊 let slow = head let fast = head.next while(fast&&fast.next){ slow = slow.next fast = fast.next.next } // 分成兩邊後，將右半給反轉，並用將原始 head 的 連結給切斷 const right = reverseList(slow.next) slow.next = null merge(head, right) }; function reverseList(head){ if(!head) return null if(!head.next) return head let pre = head let cur = head.next let temp = null pre.next = null while(cur !== null){ temp = cur cur = cur.next temp.next = pre pre = temp } return pre } function merge(l1,l2){ while(l1){ // 因為是左右左右交互合併，所以要在有 l1 的狀況下進行 // 保留下原始的 l1, l2 的 next 後的狀態 // l2 是有可能會沒有 next 的，所以要判斷一下 let rawL1 = l1.next let rawL2 = l2? l2.next : null l1.next = l2 // 當 l1.next 接到 null，代表 l2 沒有了，可以跳出 if(l1.next === null){ break } l2.next = rawL1 l1 = rawL1 l2 = rawL2 } } |
148. Sort List
連結：https://leetcode.com/problems/sort-list/
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ var sortList = function(head) { if(!head || !head.next) return head let slow = head let fast = head.next while(fast && fast.next){ slow = slow.next fast = fast.next.next } const right = slow.next // 定義右半 slow.next = null // 將原始的 head 和右半切斷 // 反覆堆疊 sortList 的結果後，並將其傳入 merge 函式中作排序 return merge(sortList(head), sortList(right)) }; function merge(l1,l2){ let dummy = new ListNode(0) let curr = dummy // 兩兩比較，若 l1 比 l2 大，先將 l2 接到 cur 下，否則反之 // 接上後，更新 cur 和 l1 or l2 while(l1&&l2){ if(l1.val>l2.val){ curr.next = l2 l2 = l2.next }else{ curr.next = l1 l1 = l1.next } curr = curr.next } // 如果其中 l1, 接完了，那就換 l2 // 最後回傳 dummy.next 以後的結果 curr.next = l1 ? l1 : l2 return dummy.next } |
206. Reverse Linked List
連結：https://leetcode.com/problems/reverse-linked-list/
|
1 2 3 4 5 6 7 8 |
var reverseList = function(head) { if(!head || !head.next) return head let temp = head head = reverseList(temp.next) temp.next.next = temp temp.next = null return head }; |
