Here is one way to determine if two singly lists intersect in JavaScript:
intersectionTry in REPL1 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 57
| function intersection(list1, list2) { let len1 = 0; let len2 = 0; let l1 = list1; let l2 = list2; let tail1, tail2; while (l1) { len1++; if (!l1.next) tail1 = l1; l1 = l1.next; } while (l2) { len2++; if (!l2.next) tail2 = l2; l2 = l2.next; } if (tail1 !== tail2) return null; let lenDiff = Math.abs(len2-len1); if (len2 > len1) { while (lenDiff--) { list2 = list2.next; } } else { while (lenDiff--) { list1 = list1.next; } } while (list1 && list2) { if (list1 === list2) return list1; list1 = list1.next; list2 = list2.next; } } function Node(data) { this.next = null; this.data = data; } Node.prototype.addToTail = function(data) { const end = new Node(data); let current = this; while (current.next !== null) { current = current.next; } current.next = end; return end; };
|
Tests can be found at REPL.it