LeetCode 在需要接觸演算碼的工程師中，為相當知名的練習場所。當你有需要挑戰自己的腦筋、面試前的準備……等，都滿適合來這邊看一下你的演算法和資料結構的熟悉程度。這回要筆記的有 Merge Two Sorted Lists、Reverse Linked List、Middle of the Linked List。
題目
21. Merge Two Sorted Lists
[連結]：https://leetcode.com/problems/merge-two-sorted-lists/
|
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 |
/* * 1. 建立一個 result 的 nodeList，並將所有要新增的 node 都接在其後，統一回傳 result.next * 2. l1, l2 比較 * 3. 如果其中一個 list 沒有了，那麼就將剩下的全部接到 currentNode.next */ var mergeTwoLists = function(l1, l2) { let result = new ListNode(0) let currentNode = result while(l1 !== null && l2 !== null){ if(l1.val < l2.val){ currentNode.next = l1 l1 = l1.next }else{ currentNode.next = l2 l2 = l2.next } currentNode = currentNode.next } if(l1 !== null){ currentNode.next = l1 } if(l2 !== null){ currentNode.next = l2 } return result.next }; |
206. Reverse Linked List
[連結]：https://leetcode.com/problems/reverse-linked-list/
A. 如果沒有 head ，回傳 null
B. 如果 head.next 為 null，回傳 head
只要將鏈結的指向順序全部反轉就好，所以……
1. 從左到右開始，把 head 值用 pre 保存, head.next 用 cur 保存, 並新增一個 temp = null
2. 將 pre.next 改為 null
3. 當 cur 不為 null ，表示還沒走完全程，所以……
I. 將 cur 的現在狀態給 temp 保存
II. 將 cur.next 變成 cur，這樣一來就把原先的 cur 和 cur.next 的連結切斷
III. 將 temp.next 接到 pre 上
IV. 由於 temp 保留了最一開始 cur.val 的狀態，所以會 temp 成為新的 pre
4. 最後印出 pre ，反轉完成
|
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 |
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function(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 }; |
876. Middle of the Linked List
[連結]：https://leetcode.com/problems/middle-of-the-linked-list/
1. 用 while 迴圈搭配 counter 記下全部的 Link 長度
2. 接著取中點，若奇數則向下取整數、偶數則向上取整數
3. 按照剩餘的 counter 值移動 head，每移動一次就 – 1
|
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 |
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var middleNode = function(head) { let counter = 1 let pointer = head while(pointer.next !== null){ pointer = pointer.next counter++ } counter % 2 === 0 ? counter = Math.ceil(counter / 2) : counter = Math.floor(counter / 2) while(counter>0){ head = head.next counter-- } return head }; |
