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 is 0 if there is no intersected node.listA - The first linked list.listB - The second linked list.skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.skipB - The number of nodes to skip ahead in listB (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:
listA is in the m.listB is in the n.1 <= m, n <= 3 * 1041 <= Node.val <= 1050 <= skipA <= m0 <= skipB <= nintersectVal is 0 if listA and listB do not intersect.intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.O(m + n) time and use only O(1) memory?The goal in Intersection of Two Linked Lists is to determine the node where two singly linked lists intersect. Since the lists may have different lengths, the key challenge is aligning traversal so both pointers can reach the intersection point at the same time.
One intuitive method uses a Hash Table. Traverse the first list and store each node reference in a set. Then iterate through the second list and check whether a node already exists in the set. The first match indicates the intersection node.
A more optimal technique uses the Two Pointers approach. Start two pointers at the heads of both lists and move them forward. When a pointer reaches the end of its list, redirect it to the head of the other list. This clever switching aligns the traversal lengths, ensuring both pointers meet at the intersection node if it exists.
The two-pointer strategy runs in O(m+n) time and uses O(1) extra space, making it the preferred interview solution.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Table | O(m + n) | O(m) |
| Two Pointers (Optimal) | O(m + n) | O(1) |
NeetCode
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).
1public class Solution {
2 public class ListNode {
3 public int val;
4 public ListNode next;
5 public ListNode(int x) { val = x; next = null; }
6 }
7
8 private int GetLength(ListNode head) {
9 int length = 0;
10 while (head != null) {
11 length++;
12 head = head.next;
13 }
14 return length;
15 }
16
17 public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
18 int lenA = GetLength(headA);
19 int lenB = GetLength(headB);
20
21 if (lenA > lenB) {
22 for (int i = 0; i < lenA - lenB; i++) headA = headA.next;
23 } else {
24 for (int i = 0; i < lenB - lenA; i++) headB = headB.next;
25 }
26
27 while (headA != headB) {
28 headA = headA.next;
29 headB = headB.next;
30 }
31 return headA;
32 }
33}The C# solution makes use of an auxiliary function to calculate the lengths of the linked lists, adjusts one of the heads if needed, and searches for the intersection node.
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#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
When each pointer switches to the head of the other list after reaching the end, both pointers effectively traverse the same total distance (m+n). This alignment ensures that if an intersection exists, the pointers will meet exactly at that node.
Yes, this problem is commonly asked in technical interviews at companies like Amazon, Google, and Meta. It tests understanding of linked list traversal, pointer manipulation, and the ability to optimize space complexity.
The optimal solution uses the two-pointer technique. Each pointer traverses both linked lists by switching heads when reaching the end. This equalizes path lengths and allows both pointers to meet at the intersection node in O(m+n) time with O(1) space.
A hash set can be used to store nodes from the first linked list and quickly check whether nodes from the second list already exist. However, while this approach is simple, it requires additional memory. The two-pointer technique is generally preferred because it uses constant space.
This implementation uses two pointers initialized to the heads of the two lists. Each pointer traverses its list and switches to the other list once it reaches the end. They meet at the intersection node or at null if there is none.