Log inSign up
easyLeetCodeNot Started

Intersection of Two Linked Lists

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Linked List
Solve on LeetCode
Lesson

Problem Statement

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: `` A: a1 → a2 ↘ c1 → c2 → c3 B: b1 → b2 → b3 ↗

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 in listA (starting from the head) to skip to arrive at the intersected node. - skipB - The number of nodes in listB (starting from the head) to skip to arrive at the intersected node.

Example 1 · Intersecting Lists:

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. 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.

Example 2 · No Intersection:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection (null)
Explanation: The two lists do not intersect, so return null.

Constraints:

  • The number of nodes of listA is in the m.
  • The number of nodes of listB is in the n.
  • 1 <= m, n <= 3 * 10^4
  • 1 <= Node.val <= 10^5
  • 0 <= skipA < m
  • 0 <= skipB < n
  • intersectVal == listA[skipA] if listA and listB intersect, else intersectVal == 0.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the Equi-Travel Principle for aligning asynchronous linear traversals.
  • Distinguish between value equality (a.val == b.val) and reference identity (a == b).
  • Eliminate explicit length counting through bidirectional pointer redirecting.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding shared node references (by address/identity, not just value) between two linked lists.
  • Unbalanced list lengths leading to a shared tail.
  • Requirement to preserve original lists and achieve O(1) memory.

Algorithmic Decision Tree:

  • If allowed extra memory, store list A's node addresses in a Hash Set and check membership for list B.
  • For optimal O(1) space, either calculate length difference |lenA - lenB| and offset the longer list, or use the elegant two-pointer switching technique.

Connected Patterns:

Linked List Cycle II (Floyd's Tortoise and Hare)Lowest Common Ancestor in a Binary Tree

1. Brute Force — Hash Set Node Address Lookup

Intuition

Record every node pointer from list A in a hash set. Walk list B and return the first node pointer that is present in the set.

Algorithm

  1. Step 1: Create an empty HashSet of node pointers.
  2. Step 2: Traverse currA from headA, adding each node address to the set.
  3. Step 3: Traverse currB from headB. If set.contains(currB), return currB.
  4. Step 4: If end of list B is reached without a match, return null.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <unordered_set>
3
4using namespace std;
5
6struct ListNode {
7 int val;
8 ListNode *next;
9 ListNode(int x) : val(x), next(nullptr) {}
10};
11
12class Solution {
13public:
14 ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
15 unordered_set<ListNode*> visited;
16 ListNode* currA = headA;
17 while (currA) {
18 visited.insert(currA);
19 currA = currA->next;
20 }
21
22 ListNode* currB = headB;
23 while (currB) {
24 if (visited.count(currB)) {
25 return currB;
26 }
27 currB = currB->next;
28 }
29 return nullptr;
30 }
31};
32
33int main() {
34 ListNode* c1 = new ListNode(8);
35 ListNode* c2 = new ListNode(4);
36 ListNode* c3 = new ListNode(5);
37 c1->next = c2; c2->next = c3;
38
39 ListNode* a1 = new ListNode(4);
40 ListNode* a2 = new ListNode(1);
41 a1->next = a2; a2->next = c1;
42
43 ListNode* b1 = new ListNode(5);
44 ListNode* b2 = new ListNode(6);
45 ListNode* b3 = new ListNode(1);
46 b1->next = b2; b2->next = b3; b3->next = c1;
47
48 Solution sol;
49 ListNode* inter = sol.getIntersectionNode(a1, b1);
50 cout << "Brute Force Intersection: " << (inter ? to_string(inter->val) : "null") << endl;
51 return 0;
52}

Time & Space Complexity

  • Time complexity: O(N + M) — Inserts all N nodes of list A into a hash set in O(N), then queries for M nodes of list B in O(M).
  • Space complexity: O(N) — Stores N node references in the hash table.

Why Brute Force Doesn't Scale:

Hash set stores N references, incurring hash table allocation overhead.

For N = 30,000 and M = 30,000, two pointers use 0 extra bytes and complete in <0.5ms.

2. Better — Length Difference & Head Alignment

Intuition

Count length of list A (lenA) and list B (lenB). Advance the pointer of the longer list by |lenA - lenB| steps. Now both pointers are equidistant from the intersection point (or the end). Walk both pointers together step by step until they match.

Algorithm

  1. Step 1: Compute lengths lenA and lenB by traversing each list.
  2. Step 2: Reset pA = headA and pB = headB.
  3. Step 3: If lenA > lenB, advance pA by lenA - lenB steps.
  4. Step 4: If lenB > lenA, advance pB by lenB - lenA steps.
  5. Step 5: While pA != null && pB != null:
  6. a. If pA == pB, return pA.
  7. b. Advance pA = pA.next, pB = pB.next.
  8. Step 6: Return null.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <cmath>
3
4using namespace std;
5
6struct ListNode {
7 int val;
8 ListNode *next;
9 ListNode(int x) : val(x), next(nullptr) {}
10};
11
12class Solution {
13 int getLength(ListNode* head) {
14 int len = 0;
15 while (head) {
16 len++;
17 head = head->next;
18 }
19 return len;
20 }
21public:
22 ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
23 int lenA = getLength(headA);
24 int lenB = getLength(headB);
25
26 ListNode* pA = headA;
27 ListNode* pB = headB;
28
29 while (lenA > lenB) {
30 pA = pA->next;
31 lenA--;
32 }
33 while (lenB > lenA) {
34 pB = pB->next;
35 lenB--;
36 }
37
38 while (pA && pB) {
39 if (pA == pB) return pA;
40 pA = pA->next;
41 pB = pB->next;
42 }
43 return nullptr;
44 }
45};
46
47int main() {
48 ListNode* c1 = new ListNode(8);
49 ListNode* a1 = new ListNode(4);
50 a1->next = c1;
51 ListNode* b1 = new ListNode(5);
52 b1->next = c1;
53
54 Solution sol;
55 ListNode* inter = sol.getIntersectionNode(a1, b1);
56 cout << "Length Diff Intersect: " << (inter ? to_string(inter->val) : "null") << endl;
57 return 0;
58}

Time & Space Complexity

  • Time complexity: O(N + M) — Computes lengths in O(N + M), advances difference in O(|N - M|), and walks together in O(min(N, M)). Strict O(N + M) total time.
  • Space complexity: O(1) — Operates strictly in-place with O(1) auxiliary pointers.

3. Optimal — Two-Pointer Pointer Switching (A + B = B + A)

Intuition

Let pointer pA start at headA and pB start at headB. Advance both by one node at each step. When pA reaches null, redirect it to headB. When pB reaches null, redirect it to headA. Because lenA + lenB == lenB + lenA, both pointers travel equal total distance and meet at the intersection node or both hit null simultaneously.

Algorithm

  1. Step 1: If headA == null || headB == null, return null.
  2. Step 2: Initialize pA = headA and pB = headB.
  3. Step 3: While pA != pB:
  4. a. If pA == null, set pA = headB; else pA = pA.next.
  5. b. If pB == null, set pB = headA; else pB = pB.next.
  6. Step 4: Return pA (which is either the intersection node or null).

Intersection of Two Linked Lists Master Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
pA now starts traversing list B
Visual state
Values and pointers at this exact step
linked list
pA → nullpB → 5_tail
Node 4a
4
Node 1a
1
Node 8
8 (target)
Node 4b
4
Node 5
5
NULL
Check / comparison
pA reached null
Decision / next transition
Redirect pA to headB
Why this step matters

pA now starts traversing list B.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5struct ListNode {
6 int val;
7 ListNode *next;
8 ListNode(int x) : val(x), next(nullptr) {}
9};
10
11class Solution {
12public:
13 ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
14 if (!headA || !headB) return nullptr;
15
16 ListNode* pA = headA;
17 ListNode* pB = headB;
18
19 while (pA != pB) {
20 pA = (pA == nullptr) ? headB : pA->next;
21 pB = (pB == nullptr) ? headA : pB->next;
22 }
23
24 return pA;
25 }
26};
27
28int main() {
29 ListNode* c1 = new ListNode(8);
30 ListNode* c2 = new ListNode(4);
31 ListNode* c3 = new ListNode(5);
32 c1->next = c2; c2->next = c3;
33
34 ListNode* a1 = new ListNode(4);
35 ListNode* a2 = new ListNode(1);
36 a1->next = a2; a2->next = c1;
37
38 ListNode* b1 = new ListNode(5);
39 ListNode* b2 = new ListNode(6);
40 ListNode* b3 = new ListNode(1);
41 b1->next = b2; b2->next = b3; b3->next = c1;
42
43 Solution sol;
44 ListNode* inter = sol.getIntersectionNode(a1, b1);
45 cout << "Optimal Pointer Switch Intersect: " << (inter ? to_string(inter->val) : "null") << endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(N + M) — Each pointer takes at most N + M steps. If they intersect, they meet in the second pass; if they do not intersect, both become null after N + M steps.
  • Space complexity: O(1) — Uses exactly two pointer references (pA, pB) with zero heap allocation.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Hash Set Node Address LookupO(N + M)O(N)Traverse List A and store every node memory address in a Hash Set. Then traverse List B and check if any node address exists in the set. The first match is the intersection.Memory allocation for hash set.
2.Better — Length Difference & Head AlignmentO(N + M)O(1)Count length lenA and lenB. Advance the pointer of the longer list by |lenA - lenB| steps so both pointers are equidistant from the tail. Then advance both pointers simultaneously until they meet.Multiple traversal passes.
3.Optimal — Two-Pointer Pointer Switch (A+B = B+A)OptimalO(N + M)O(1)Initialize pA = headA and pB = headB. In each step, if pA == pB, return pA. Otherwise, advance pA = pA ? pA.next : headB and pB = pB ? pB.next : headA. Both pointers traverse lenA + lenB nodes and meet simultaneously.Optimal.

Common Pitfalls & Crucial Edge Cases

Comparing values instead of references

Checking pA.val == pB.val returns false intersections if two distinct nodes happen to hold the same number.

Resetting at the wrong time

Resetting pA when pA.next == null instead of when pA == null skips the null-check condition and can cause infinite loops when lists don't intersect.

Modifying list structure

Attempting to reverse or alter links when the problem requires lists to remain unchanged.

Crucial Edge Cases to Validate:

  • No Intersection — Both pointers traverse lenA + lenB nodes, become null at the exact same step, and the loop terminates returning null.
  • Same Head (Identical Lists) — pA == pB on the first iteration -> returns headA in O(1).
  • One List is Sublist of Other — Intersection is at headA or headB -> properly detected after length offset.
  • One List is Empty — headA == null || headB == null -> returns null immediately.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the mathematical proof upfront: 'Path A + Path B equals Path B + Path A. Both pointers travel equal distance and synchronize at the intersection suffix.'
  2. Emphasize that the condition is pA == null ? headB : pA.next (not pA.next == null), so that the non-intersecting case naturally terminates at pA == pB == null.
  3. Clarify that node references (not values) are compared.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do the two pointers meet at null if the two lists do not intersect?

2.What is the key difference between checking pA.val == pB.val versus pA == pB?

3.What is the maximum number of pointer step operations performed by the optimal two-pointer solution?

Back to DSA Sheet