How to Answer: Where do the two linked lists intersect?
Advice and answer examples written specifically for a Java Intermediate Level Linked Lists job interview.
3. Where do the two linked lists intersect?
This question focuses on working with Java lists.
You are given heads of two singly linked lists: headA and headB. Your task is to return the node at which they intersect each other. If they don’t intersect, return null.
It is guaranteed that there is no cycle in any of the lists. Please note the linked lists MUST retain their original structure after the function returns.
/*Example*/
Given lists:
headA: 4 -> 1
\
8 -> 7 -> 9
/
headB: 5 -> 2 -> 3 -> 10
Expected output: 8
Explanation: Since both of the lists intersect at node 8, we return 8
Given lists:
headA: 4 -> 1 -> 8 -> 4 -> 5
headB: 5 -> 2 -> 3 -> 8 -> 4 -> 5
Expected output: null
Explanation: The lists do not intersect.Solution:
Approach I (finding length)
First, we will find the lengths of the two lists using function listLength. Then we will align headA and headB such that the length of the list after points headA and headB is the same. For the first example:
lenA = 5
lenB = 7
We move headB two steps ahead to point to node with value 3 such that lengths after headA and headB are the same, that is 5.
After aligning the nodes, we iterate over both lists simultaneously and will find the same node. At each iteration, we advance both headA and headB if previous values were not equal. We break the loop as soon as the values of headA and headB are the same which means it is the intersection node.
If the lists do not intersect, the values of headA and headB will be null at last, which will break the loop and will return null.
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lenA = listLength(headA);
int lenB = listLength(headB);
// if listA is of more length,
// advance headA so that it aligns to headB
while(lenA > lenB) {
headA = headA.next;
lenA--;
}
// if listB is of more length,
// advance headB so that it aligns to headA
while(lenB > lenA) {
headB = headB.next;
lenB--;
}
while(headA != headB) {
headA = headA.next;
headB = headB.next;
}
return headA;
}
private int listLength(ListNode head) {
int len = 0;
while(head != null) {
head = head.next;
len++;
}
return len;
}
}n = length the linked list
Time complexity- O(n)
Space complexity- O(1)
Approach II (without finding the length):
In the previous approach, we found the lengths of the lists and then aligned them. In this approach, we will do this without actually finding the lengths of the lists.
Let's denote the two lists by list A and list B. Let’s take two pointers: pointer1 and pointer2. Pointer1 starts from the head of list A and pointer2 starts from the head of list B. In each step, we advance both the pointers one by one.
pointer1
|
A:- -------------
|----
B:- ------------------
|
pointer2
Since list A is shorter, pointer1 will reach the end first; we will point it to the head of list B and start advancing it in the same way.
A: -------------
|----
B: ------------------ |
| |
pointer1 pointer2
After some time, pointer2 will reach the end of list B; we will point it to the head of list A and start advancing it in the same way. At this point, pointer1 is traversing list B and pointer2 is traversing list A.
pointer2
|
A: -------------
|----
B: ------------------
|
pointer1
Now we will advance both pointers in the same way:- advance both pointers by one step simultaneously. In this type, both the pointer will reach the intersection at the same time. This will break the loop and will return the intersection node. If the lists do intersect, both pointers will be null at the end simultaneously, which will break the loop and return null.
Proof
Let us have two lists A and B with length len_a and len_b. Also assume list A is shorter than list B i.e., len_a < len_b
Let both the lists intersect each other and comm_len be the 1length of their common part.
|<====== len_a =====>|
A:- -----------------
|----
B:- ----------------------
|<==>| comm_len
|<======== len_b =========>|
When pointer1 reaches the end of list A, pointer1 and pointer2 have traversed len_a number of nodes.
When pointer2 reaches the end of list B, pointer1 and pointer2 have traversed len_b number of nodes. Or we can say that pointer1 traversed len_a number of nodes of list A and (len_b - len_a) number of nodes of list B; so total len_b number of nodes.
When both the pointers reach the intersection:
Number of nodes traversed by pointer1: len_a + (len_b - comm_len)
| |
of list A of list B
Number of nodes traversed by pointer1: len_b + (len_a - comm_len)
| |
of list B of list A
, which is the same. So both pointers are guaranteed to reach the intersection node during the second pass.
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
public class Solution {
public ListNode getIntersectionNode(ListNode headA,
ListNode headB) {
ListNode pointer1 = headA;
ListNode pointer2 = headB;
while(pointer1 != pointer2) {
pointer1 = pointer1 == null ? headB : pointer1.next;
pointer2 = pointer2 == null ? headA : pointer2.next;
}
return pointer1;
}
}n = length the linked list
Time complexity- O(n)
Space complexity- O(1)
Written by S. Kumar on May 22nd, 2021