Sponsored
Sponsored
First, traverse both linked lists to determine their lengths. Calculate the difference in lengths and advance the pointer of the longer list by the length difference. Then move both pointers in tandem to find the intersection node.
Time Complexity: O(m + n).
Space Complexity: O(1).
1function ListNode(val) {
2 this.val = val;
3 this.next = null;
4}
5
6function getLength(head) {
7 let length = 0;
8 while (head) {
9 length++;
10 head = head.next;
11 }
12 return length;
13}
14
15function getIntersectionNode(headA, headB) {
16 let lenA = getLength(headA);
17 let lenB = getLength(headB);
18
19 if (lenA > lenB) {
20 for (let i = 0; i < lenA - lenB; i++) headA = headA.next;
21 } else {
22 for (let i = 0; i < lenB - lenA; i++) headB = headB.next;
23 }
24
25 while (headA !== headB) {
26 headA = headA.next;
27 headB = headB.next;
28 }
29 return headA;
30}The JavaScript implementation calculates the lengths of the two linked lists, compensates for the difference in lengths if any, and checks node by node for intersection.
Use two pointers, each starting at the head of one list. Traverse the list until a pointer reaches null, then start traversing the other list from the beginning. Repeat until the two pointers meet at the intersection node.
Time Complexity: O(m + n).
Space Complexity: O(1).
1
The JavaScript implementation uses two pointers that travel through both lists. They alternate between lists at the end of each traversal until they meet at the intersection point or return null if no intersection exists.