Problem
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
begin to intersect at node c1.
Notes:
- If the two linked lists have no intersection at all, return
null
. - The linked lists must retain their original structure after the function returns.
- You may assume there are no cycles anywhere in the entire linked structure.
- Your code should preferably run in O(n) time and use only O(1) memory.
Credits:Special thanks to @stellari for adding this problem and creating all test cases.
Solution 1
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function(headA, headB) {
var lenA = getLen(headA);
var lenB = getLen(headB);
let diff = Math.abs(lenA - lenB);
if (lenA > lenB) {
while (diff--) headA = headA.next;
} else {
while (diff--) headB = headB.next;
}
while (headA !== headB) {
headA = headA.next;
headB = headB.next;
}
return headA;
};
var getLen = function (head) {
var len = 0;
while (head) {
len++;
head = head.next;
}
return len;
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(1).
Solution 2
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function(headA, headB) {
if (!headA || !headB) return null;
var nowA = headA;
var nowB = headB;
while (nowA !== nowB) {
nowA = nowA ? nowA.next : headB;
nowB = nowB ? nowB.next : headA;
}
return nowA;
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(1).