Intersection Point of Two Linked Lists in DSA Java

Mental Model

Two linked lists may share some nodes at the end, forming an intersection. We want to find the first shared node.

Analogy: Imagine two roads that start separately but merge into one road at some point. We want to find the exact spot where they join.

List A: 1 -> 2 -> 3 -> 4 -> 5 -> null
                     ↑
List B:       9 -> 4 -> 5 -> null

Dry Run Walkthrough

Input: List A: 1->2->3->4->5, List B: 9->4->5 (4 and 5 are shared nodes)

Goal: Find the node where both lists start to share nodes (node with value 4).

Step 1: Calculate lengths of both lists: lenA=5, lenB=3

List A: 1 -> 2 -> 3 -> 4 -> 5 -> null
List B: 9 -> 4 -> 5 -> null

Why: Knowing lengths helps align both lists to the same remaining length.

Step 2: Advance pointer in longer list (A) by difference (2 steps)

List A pointer at node 3 -> 4 -> 5 -> null
List B pointer at node 9 -> 4 -> 5 -> null

Why: Align both pointers so they have equal nodes left to traverse.

Step 3: Compare nodes at pointers: 3 vs 9 (not same), move both forward

List A pointer at 4 -> 5 -> null
List B pointer at 4 -> 5 -> null

Why: Move forward to find intersection.

Step 4: Compare nodes at pointers: 4 vs 4 (same node), intersection found

Intersection node: 4 -> 5 -> null

Why: First common node is the intersection point.

Result:

4 -> 5 -> null is the intersection point

Annotated Code

DSA Java

public class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}

public class Intersection {
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = getLength(headA);
        int lenB = getLength(headB);

        // Align heads
        while (lenA > lenB) {
            headA = headA.next; // advance headA to align
            lenA--;
        }
        while (lenB > lenA) {
            headB = headB.next; // advance headB to align
            lenB--;
        }

        // Move both pointers until intersection or end
        while (headA != null && headB != null) {
            if (headA == headB) {
                return headA; // intersection found
            }
            headA = headA.next; // advance both
            headB = headB.next;
        }
        return null; // no intersection
    }

    private static int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next; // advance to count length
        }
        return length;
    }

    public static void main(String[] args) {
        // Shared nodes
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node4.next = node5;

        // List A: 1->2->3->4->5
        ListNode headA = new ListNode(1);
        headA.next = new ListNode(2);
        headA.next.next = new ListNode(3);
        headA.next.next.next = node4;

        // List B: 9->4->5
        ListNode headB = new ListNode(9);
        headB.next = node4;

        ListNode intersection = getIntersectionNode(headA, headB);
        if (intersection != null) {
            printList(intersection); // print from intersection
        } else {
            System.out.println("No intersection");
        }
    }

    private static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val);
            if (head.next != null) System.out.print(" -> ");
            head = head.next;
        }
        System.out.println(" -> null");
    }
}

int lenA = getLength(headA); int lenB = getLength(headB);

Calculate lengths of both lists to find difference

while (lenA > lenB) { headA = headA.next; lenA--; }

Advance longer list pointer to align both lists

while (lenB > lenA) { headB = headB.next; lenB--; }

Advance longer list pointer to align both lists

while (headA != null && headB != null) { if (headA == headB) return headA; headA = headA.next; headB = headB.next; }

Traverse both lists together to find intersection node

Output

4 -> 5 -> null

Complexity Analysis

Time: O(m + n) because we traverse both lists to get lengths and then traverse aligned parts once

Space: O(1) because we use only pointers and counters, no extra data structures

vs Alternative: Naive approach compares every node of one list with every node of the other, O(m*n), much slower

Edge Cases

One or both lists are empty

Returns null immediately, no intersection

DSA Java

while (headA != null && headB != null) { ... }

Lists do not intersect

Returns null after traversing both lists

DSA Java

return null; // no intersection

Intersection at head node

Returns head node immediately

DSA Java

if (headA == headB) return headA;

When to Use This Pattern

When two linked lists may share nodes and you need to find the first shared node, use the length alignment pattern to find intersection efficiently.

Common Mistakes

Mistake: Comparing node values instead of node references for intersection
Fix: Compare nodes by reference (headA == headB), not by value

Mistake: Not aligning the longer list pointer before traversal
Fix: Calculate lengths and advance longer list pointer by difference before simultaneous traversal

Summary

Finds the first shared node where two linked lists intersect.

Use when two linked lists may merge and you want to find their joining point.

Align list pointers by length difference, then traverse together to find intersection.

Practice

1. What does the term intersection point of two linked lists mean?

easy

A. The node where both linked lists share the same reference (memory address).

B. The node where the values of both linked lists are equal.

C. The first node of the longer linked list.

D. The last node of the shorter linked list.

Solution

1. Step 1: Understand linked list nodes

   Each node in a linked list has a value and a reference (memory address) to the next node.

2. Step 2: Define intersection point

   The intersection point is where two linked lists share the exact same node reference, meaning they merge at that node.

3. Final Answer:

   The node where both linked lists share the same reference (memory address). -> Option A

4. Quick Check:

   Intersection means shared node reference [OK]

Hint: Intersection means same node object, not just same value [OK]

Common Mistakes:

• Confusing same value with same node reference
• Thinking intersection is about list length
• Assuming intersection is always at the last node

2. Which of the following Java method signatures correctly represents a function to find the intersection point of two singly linked lists?

easy

A. public ListNode getIntersectionNode(int headA, int headB)

B. public void getIntersectionNode(ListNode headA, ListNode headB)

C. public int getIntersectionNode(ListNode headA, ListNode headB)

D. public ListNode getIntersectionNode(ListNode headA, ListNode headB)

Solution

1. Step 1: Understand method return type

   The method should return the intersecting node, so return type must be ListNode.

2. Step 2: Check parameter types

   Parameters must be the heads of the two linked lists, which are ListNode references.

3. Final Answer:

   public ListNode getIntersectionNode(ListNode headA, ListNode headB) -> Option D

4. Quick Check:

   Return node, input heads as ListNode [OK]

Hint: Return the intersecting node, input heads as ListNode [OK]

Common Mistakes:

• Using void return type instead of ListNode
• Using primitive types instead of ListNode
• Incorrect parameter types

3. Consider the following Java code snippet to find the intersection point of two linked lists:

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;
}

If the two linked lists intersect at node with value 8, what will be the output when printing getIntersectionNode(headA, headB).val?

medium

A. 0

B. 8

C. null

D. Runtime error

Solution

1. Step 1: Understand the two-pointer approach

   Two pointers traverse each list; when one reaches end, it switches to the other list's head. They meet at intersection.

2. Step 2: Identify intersection value

   Since lists intersect at node with value 8, pointers meet there and return that node.

3. Final Answer:

   8 -> Option B

4. Quick Check:

   Two-pointer meet at intersection node value 8 [OK]

Hint: Two pointers meet at intersection node value [OK]

Common Mistakes:

• Assuming output is null if lists differ in length
• Confusing node value with node reference
• Not understanding pointer switching logic

4. The following code attempts to find the intersection point of two linked lists but has a bug:

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    while (headA != headB) {
        headA = headA.next;
        headB = headB.next;
    }
    return headA;
}

What is the main problem with this code?

medium

A. It does not handle different list lengths, causing NullPointerException.

B. It uses incorrect comparison operator for nodes.

C. It returns the wrong node even if lists intersect.

D. It modifies the original lists, which is not allowed.

Solution

1. Step 1: Analyze pointer movement

   Both pointers move forward without switching lists, so if lengths differ, one pointer reaches null first.

2. Step 2: Identify error cause

   When one pointer is null and the other is not, accessing next causes NullPointerException.

3. Final Answer:

   It does not handle different list lengths, causing NullPointerException. -> Option A

4. Quick Check:

   Different lengths cause null access error [OK]

Hint: Handle different lengths by switching pointers [OK]

Common Mistakes:

• Ignoring list length difference
• Assuming nodes with same value are intersection
• Not checking for null before accessing next

5. You have two singly linked lists that intersect. List A has length 5, List B has length 7. Which approach correctly finds the intersection point in O(n) time without extra space?

hard

A. Use a hash set to store nodes of List A, then check nodes of List B.

B. Reverse both lists and compare nodes from the start.

C. Calculate lengths, advance longer list by difference, then move both pointers together.

D. Traverse both lists simultaneously without adjusting for length difference.

Solution

1. Step 1: Calculate lengths and difference

   Find lengths of both lists and compute difference (7 - 5 = 2).

2. Step 2: Advance longer list pointer

   Move pointer of longer list (List B) ahead by difference to align both pointers equally from intersection.

3. Step 3: Move both pointers together to find intersection

   Advance both pointers one step at a time until they meet at intersection node.

4. Final Answer:

   Calculate lengths, advance longer list by difference, then move both pointers together. -> Option C

5. Quick Check:

   Align pointers by length difference for O(n) solution [OK]

Hint: Advance longer list by length difference before simultaneous traversal [OK]

Common Mistakes:

• Using extra space like hash sets (not O(1) space)
• Reversing lists which is inefficient and modifies data
• Not adjusting for length difference causing wrong results