LeetCode 在需要接觸演算碼的工程師中，為相當知名的練習場所。當你有需要挑戰自己的腦筋、面試前的準備……等，都滿適合來這邊看一下你的演算法和資料結構的熟悉程度。這回要筆記的有 Linked List Cycle、Intersection of Two Linked Lists、Palindrome Linked List。
題目
141. Linked List Cycle
[連結]：https://leetcode.com/problems/linked-list-cycle/
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
/* * 1. 一個個 node 逐步遍歷，拜訪過的給個 flag 為 true * 2. 如果之後有讀到為 true 的，那就是有形成 cycle */ var hasCycle = function(head) { if(head === null || head.next === null) return false let node = head; while(node !== null){ if(node.flag) return true node.flag = true node = node.next } return false }; |
160. Intersection of Two Linked Lists
[連結]：https://leetcode.com/problems/intersection-of-two-linked-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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
/** * 1. 先取出 headA, headB 的長度差距 * 2. 如果 headA 比較長，則略過過長的部分；反之亦然 * 3. 當兩個長度一樣後，就開始遍歷：如果兩個有相同，就回傳該值。 */ var getIntersectionNode = function(headA, headB) { let diffValue = getDifference(headA, headB) if(diffValue > 0){ while(diffValue > 0){ headA = headA.next diffValue -= 1 } }else{ while(diffValue < 0){ headB = headB.next diffValue += 1 } } while(headA !== null){ if(headA === headB) return headA headA = headA.next headB = headB.next } return null }; function getDifference(nodeA,nodeB){ let lengthA = 0 let lengthB = 0 while(nodeA !== null){ lengthA += 1 nodeA = nodeA.next } while(nodeB !== null){ lengthB += 1 nodeB = nodeB.next } return lengthA - lengthB } |
234. Palindrome Linked List
[連結]：https://leetcode.com/problems/palindrome-linked-list/
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
/** * 1. 命名兩個變數，一個遍歷時從前面加入字串，另一個反之 * 2. 比較兩個結果 */ var isPalindrome = function(head) { let str1 = "" let str2 = "" while(head !== null){ str1 += head.val str2 = head.val + str2 head = head.next } return str1 === str2 }; |
