Intersection of Two Linked Lists
EasyPrompt
Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.
For example, the following two linked lists begin to intersect at node c1:
The test cases are generated such that there are no cycles anywhere in the entire linked structure.
Note that the linked lists must retain their original structure after the function returns.
Custom Judge:
The inputs to the judge are given as follows (your program is not given these inputs):
intersectVal- The value of the node where the intersection occurs. This is0if there is no intersected node.listA- The first linked list.listB- The second linked list.skipA- The number of nodes to skip ahead inlistA(starting from the head) to get to the intersected node.skipB- The number of nodes to skip ahead inlistB(starting from the head) to get to the intersected node.
The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.
Example 1:
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
- Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2nd node in A and 3rd node in B) are different node references. In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point to the same location in memory.Example 2:
Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'
Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.Example 3:
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.
Constraints:
- The number of nodes of
listAis in them. - The number of nodes of
listBis in then. 1 <= m, n <= 3 * 1041 <= Node.val <= 1050 <= skipA <= m0 <= skipB <= nintersectValis0iflistAandlistBdo not intersect.intersectVal == listA[skipA] == listB[skipB]iflistAandlistBintersect.
Follow up: Could you write a solution that runs in
O(m + n) time and use only O(1) memory?Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to iterate through every node in the first list (listA) and, for each node, iterate through every node in the second list (listB) to check if they are the same node (i.e., have the same memory reference).
Algorithm
- Initialize a pointer
ptrAtoheadA. - Loop through
listAwithptrA. - Inside this loop, start another pointer
ptrBatheadB. - Loop through
listBwithptrB. - In the inner loop, compare the pointers by reference:
if (ptrA == ptrB). - If they are the same, we have found the intersection node. Return
ptrA. - If the loops complete without finding a match, the lists do not intersect. Return
null.
Walkthrough
This method systematically checks every possible pair of nodes from the two lists. For each node in listA, it traverses the entire listB to look for a reference match. While simple, its performance degrades quadratically with the size of the lists, making it impractical for large inputs.
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode ptrA = headA; while (ptrA != null) { ListNode ptrB = headB; while (ptrB != null) { if (ptrA == ptrB) { return ptrA; } ptrB = ptrB.next; } ptrA = ptrA.next; } return null; }}Complexity
Time
O(m * n)
Space
O(1)
Trade-offs
Pros
Simple to understand and implement.
Uses constant extra space.
Cons
Highly inefficient, leading to a 'Time Limit Exceeded' error on large inputs.
A more efficient approach is to use a hash set to trade space for time. We can store all the nodes of one list in a hash set. Then, we iterate through the second list and for each node, we check if it's already in the hash set. The first node we find that is already in the set is our intersection point.
Algorithm
- Create a
HashSet<ListNode>. - Iterate through the first list (
listA) with a pointerptrA. - For each node visited, add its reference to the hash set.
- After populating the set, iterate through the second list (
listB) with a pointerptrB. - For each node visited, check if its reference exists in the hash set.
- If
set.contains(ptrB)is true, thenptrBis the intersection node. ReturnptrB. - If the second list is fully traversed without finding a match, there is no intersection. Return
null.
Walkthrough
By using a hash set, we can check for the existence of a node in O(1) average time. We first traverse one list (say, listA) and store each node's reference in the set. This takes O(m) time. Then, we traverse the second list (listB), and for each node, we check if it's in our set. The first match we find is the intersection. This second traversal takes O(n) time. The overall time complexity is therefore linear, at the cost of using extra space for the hash set.
import java.util.HashSet;import java.util.Set; public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { Set<ListNode> nodesInA = new HashSet<>(); ListNode ptrA = headA; while (ptrA != null) { nodesInA.add(ptrA); ptrA = ptrA.next; } ListNode ptrB = headB; while (ptrB != null) { if (nodesInA.contains(ptrB)) { return ptrB; } ptrB = ptrB.next; } return null; }}Complexity
Time
O(m + n)
Space
O(m)
Trade-offs
Pros
Significantly faster than the brute-force approach with linear time complexity.
Cons
Requires extra space proportional to the length of one of the lists.
The most optimal solution uses two pointers and runs in linear time with constant space. The core idea is to have two pointers traverse the lists in a way that they travel the same total distance. If they meet, they meet at the intersection. If the lists don't intersect, they will both reach the end (null) at the same time.
Algorithm
- Initialize two pointers:
ptrA = headAandptrB = headB. - Loop as long as
ptrAis not equal toptrB. - Inside the loop, advance both pointers by one step.
- A key trick is used: if a pointer reaches the end of its list (
null), it is redirected to the head of the other list. So, ifptrAbecomesnull, we setptrA = headB. IfptrBbecomesnull, we setptrB = headA. - The loop terminates when
ptrA == ptrB. The value ofptrA(orptrB) at this point is the intersection node, ornullif there is no intersection.
Walkthrough
This approach cleverly eliminates the need to calculate the lengths of the lists first. Let's say listA has a unique nodes and listB has b unique nodes, and they share c common nodes. ptrA will travel a+c nodes, then switch to headB and travel b more nodes before reaching the intersection. Total distance: a+c+b. ptrB will travel b+c nodes, then switch to headA and travel a more nodes to reach the intersection. Total distance: b+c+a. Since both pointers travel the same distance at the same speed, they are guaranteed to meet at the intersection point. If there is no intersection (c=0), ptrA travels a+b and ptrB travels b+a. They will both become null at the same time after traversing both lists, correctly returning null.
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; } ListNode ptrA = headA; ListNode ptrB = headB; while (ptrA != ptrB) { ptrA = (ptrA == null) ? headB : ptrA.next; ptrB = (ptrB == null) ? headA : ptrB.next; } return ptrA; }}Complexity
Time
O(m + n)
Space
O(1)
Trade-offs
Pros
Optimal solution with linear time and constant space complexity.
Elegant and concise implementation.
Satisfies the follow-up requirement.
Cons
The logic of why the pointers meet can be slightly non-obvious at first.
Solutions
Solution
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode getIntersectionNode ( ListNode headA , ListNode headB ) { ListNode a = headA , b = headB ; while ( a != b ) { a = a == null ? headB : a . next ; b = b == null ? headA : b . next ; } return a ; } }/** * 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) { let a = headA; let b = headB; while (a != b) { a = a ? a.next : headB; b = b ? b.next : headA; } return a; };/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode * getIntersectionNode ( ListNode * headA , ListNode * headB ) { ListNode * a = headA , * b = headB ; while ( a != b ) { a = a ? a -> next : headB ; b = b ? b -> next : headA ; } return a ; } };# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution : def getIntersectionNode ( self , headA : ListNode , headB : ListNode ) -> ListNode : a , b = headA , headB while a != b : a = a . next if a else headB b = b . next if b else headA return aVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.