Course4all
Join us on telegram
Home/dsa/Linked List Patterns/Intersection of Two Linked Lists

Intersection of Two Linked Lists

Master this topic with zero to advance depth.

Intersection of Two Linked Lists

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.

Visual Representation

List A: a1 -> a2 \ c1 -> c2 -> c3 / List B: b1 -> b2 -> b3 Intersection at c1.
Easy

Examples

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Approach 1

Level I: Brute Force (Hashing)

Intuition

Traverse the first list and store all node addresses in a hash set. Then, traverse the second list and check if any node exists in the set.

⏱ O(N + M)💾 O(N) or O(M)

Detailed Dry Run

List A: [A, B, C]. Set: {A, B, C}. List B: [D, E, B, C]. Search D (no), E (no), B (yes!). Intersection at B.

java
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    Set<ListNode> set = new HashSet<>();
    while (headA != null) { set.add(headA); headA = headA.next; }
    while (headB != null) {
        if (set.contains(headB)) return headB;
        headB = headB.next;
    }
    return null;
}

⚠️ Common Pitfalls & Tips

O(N) space is not ideal. Note that you must store node pointers/references, not just values.

Approach 2

Level II: Length Difference

Intuition

Calculate lengths of both lists. Move the pointer of the longer list forward by the difference. Then move both pointers together until they meet.

Visual Trace

A: 1 -> 2 -> 3 -> C1 (Len 4) B: 4 -> C1 (Len 2) Diff = 2. Advance pointer A by 2 steps. Pointer A starts at 3, B starts at 4. Move both: A=C1, B=C1. Match!
⏱ O(N + M)💾 O(1)

Detailed Dry Run

A: [4,1,8,4,5], B: [5,6,1,8,4,5]. LenA=5, LenB=6. Diff=1. Move B forward by 1 (to 6). Both move together: (1,1), (8,8) -> Intersect at 8.

java
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    int lenA = getLen(headA), lenB = getLen(headB);
    while (lenA > lenB) { headA = headA.next; lenA--; }
    while (lenB > lenA) { headB = headB.next; lenB--; }
    while (headA != headB) { headA = headA.next; headB = headB.next; }
    return headA;
}
private int getLen(ListNode h) {
    int l = 0; while (h != null) { l++; h = h.next; } return l;
}
Approach 3

Level III: Optimal (Two Pointers)

Intuition

Use two pointers, pA and pB. Traverse both lists. When a pointer reaches the end, redirect it to the head of the other list. They will meet at the intersection point or both become null.

⏱ O(N + M)💾 O(1)

Detailed Dry Run

A: [1,2,c], B: [3,c].

  1. pA=1, pB=3.
  2. pA=2, pB=c.
  3. pA=c, pB=null->pA=1.
  4. pA=null->pB=3, pB=c. They meet after switched paths.
java
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode a = headA, b = headB;
    while (a != b) {
        a = (a == null) ? headB : a.next;
        b = (b == null) ? headA : b.next;
    }
    return a;
}

⚠️ Common Pitfalls & Tips

The pointers will meet even if there is no intersection (both will be null).

← Previous QuestionAdd Two Numbers
Next Question →Palindrome Linked List