linkedListCycle.ts (6841B)
1 /** 2 * Given head, the head of a linked list, determine if the linked list 3 * has a cycle in it. 4 * 5 * There is a cycle in a linked list if there is some node in the list 6 * that can be reached again by continuously following the next pointer. 7 * Internally, pos is used to denote the index of the node that tail's 8 * next pointer is connected to. Note that pos is not passed as a 9 * parameter. 10 * 11 * Return true if there is a cycle in the linked list. Otherwise, 12 * return false. 13 */ 14 15 export class ListNode { 16 val: number; 17 next: ListNode | null; 18 constructor(val?: number, next?: ListNode | null) { 19 this.val = val === undefined ? 0 : val; 20 this.next = next === undefined ? null : next; 21 } 22 } 23 24 /** 25 * Build a linked list from `values`. If `pos >= 0`, the tail's `next` is 26 * connected back to the node at index `pos` to form a cycle. `pos = -1` 27 * leaves the list acyclic. Returns the head (or null for an empty list). 28 */ 29 export function buildList(values: number[], pos: number): ListNode | null { 30 if (values.length === 0) return null; 31 32 const nodes = values.map((v) => new ListNode(v)); 33 for (let i = 0; i < nodes.length - 1; i++) { 34 nodes[i].next = nodes[i + 1]; 35 } 36 if (pos >= 0) { 37 nodes[nodes.length - 1].next = nodes[pos]; 38 } 39 return nodes[0]; 40 } 41 42 /** 43 * Definition for singly-linked list. 44 * class ListNode { 45 * val: number 46 * next: ListNode | null 47 * constructor(val?: number, next?: ListNode | null) { 48 * this.val = (val===undefined ? 0 : val) 49 * this.next = (next===undefined ? null : next) 50 * } 51 * } 52 */ 53 54 // First attempt 55 // 56 // Failed (only check 1 at a time, which isnt enough) 57 // Failed on case: [-21,10,17,8,4,26,5,35,33,-7,-16,27,-12,6,29,-12,5,9,20,14, 58 // 14,2,13,-24,21,23,-21,5] (should be false) 59 export function solution1(head: ListNode | null): boolean { 60 if (!head) { 61 console.log("Head is empty. Return false"); 62 return false; 63 } 64 65 let prev = null; 66 let current = head; 67 68 while (current.next) { 69 if (!current.next.next) return false; 70 71 console.log( 72 `Current: ${current.val}, next: ${current.next.val}, next's next ${current.next.next.val}`, 73 ); 74 75 prev = current; 76 current = current.next; 77 78 if (prev.next === current) { 79 console.log(`Prev's next: ${prev.next.val} === Current: ${current.val}`); 80 return true; 81 } 82 } 83 84 return false; 85 } 86 87 // Second attempt (two-pointer / sliding-window in same direction to detect 88 // lapse) 89 // 90 // Failed (only checks 2 at a time, which isnt enough) 91 // Failed on case [1,1,1,1] (should be false) 92 export function solution2(head: ListNode | null): boolean { 93 console.log("===================="); 94 console.log("Running test"); 95 96 if (!head) { 97 console.log("Test is empty"); 98 return false; 99 } 100 101 let next = head.next; 102 if (!next) { 103 console.log("Test only has 1 element, which isn't a cycle by default."); 104 return false; 105 } 106 107 // Log the current head and the next head 108 console.log( 109 `Head ${head.val}, next ${next.val}, next's next ${next.next?.val}, next's next's next ${next.next?.next?.val}, next's next's next's next ${next.next?.next?.next?.val}, next's next's next's next's next ${next.next?.next?.next?.next?.val}`, 110 ); 111 112 let sliding_window: { a: number; b: number }[] = [ 113 { a: head.val, b: next.val }, 114 ]; 115 116 // While the list still has more vertices, keep looping through it 117 while (next) { 118 if (!next.next) { 119 console.log("The list has been exhausted without any cycles."); 120 return false; 121 } 122 123 // If the next one exists, then add the next two to the sliding windows list 124 if (next.next) { 125 let next_pair: { a: number; b: number } = { 126 a: next.val, 127 b: next.next.val, 128 }; 129 console.log("Next pair: ", next_pair); 130 131 const next_pair_already_exist = sliding_window.find( 132 (pair) => pair.a === next_pair.a && pair.b === next_pair.b, 133 ); 134 135 if (next_pair_already_exist) { 136 console.log( 137 "Sliding window list already includes the next two pairs -> cycle detected", 138 ); 139 return true; 140 } 141 142 sliding_window.push(next_pair); 143 144 // move to the next one 145 next = next.next; 146 } 147 148 console.log("Current state of the sliding Window: ", sliding_window); 149 } 150 151 console.log("Not a cycle"); 152 return false; 153 } 154 155 // Third attempt (need a verification step to verify that not only the pair 156 // exists but also is not terminating, if any pair terminates the list, then 157 // its not a cycle by default - we basically need a proof that the list doesn't 158 // terminate, even though the pairs lapse/repeat in the list) 159 // 160 // Success (Runtime: 1333ms, Memory: 63.33MB) 161 export function solution3(head: ListNode | null): boolean { 162 console.log("===================="); 163 console.log("Running test"); 164 165 if (!head) { 166 console.log("Test is empty"); 167 return false; 168 } 169 170 let next = head.next; 171 if (!next) { 172 console.log("Test only has 1 element, which isn't a cycle by default."); 173 return false; 174 } 175 176 // Log the current head and the next head 177 console.log( 178 `Head ${head.val}, next ${next.val}, next's next ${next.next?.val}, next's next's next ${next.next?.next?.val}, next's next's next's next ${next.next?.next?.next?.val}, next's next's next's next's next ${next.next?.next?.next?.next?.val}`, 179 ); 180 181 let index = 0; 182 let sliding_window: { 183 a: { val: number; pos: number }; 184 b: { val: number; pos: number }; 185 }[] = [ 186 { 187 a: { val: head.val, pos: index }, 188 b: { val: next.val, pos: index + 1 }, 189 }, 190 ]; 191 192 // While the list still has more vertices, keep looping through it 193 while (next) { 194 // Increment the index counter 195 index += 1; 196 197 if (!next.next) { 198 console.log("The list terminates without any cycles."); 199 return false; 200 } 201 202 // If the next one exists, then add the next two to the sliding windows list 203 if (next.next) { 204 let next_pair: { 205 a: { val: number; pos: number }; 206 b: { val: number; pos: number }; 207 } = { 208 a: { val: next.val, pos: index }, 209 b: { val: next.next.val, pos: index + 1 }, 210 }; 211 console.log("Next pair: ", next_pair); 212 213 const next_pair_already_exist = sliding_window.findLast( 214 (pair) => 215 pair.a.val === next_pair.a.val && pair.b.val === next_pair.b.val, 216 ); 217 218 if (next_pair_already_exist) { 219 console.log("Sliding window list already includes the next two pairs"); 220 // Check if the next pair is terminating 221 if (next.next.next && next.next.next.next) { 222 return true; 223 } else { 224 return false; 225 } 226 } 227 228 sliding_window.push(next_pair); 229 230 // move to the next one 231 next = next.next; 232 } 233 234 console.log("Current state of the sliding Window: ", sliding_window); 235 } 236 237 console.log("Not a cycle"); 238 return false; 239 }