Intersection Point of Two Linked Lists in DSA Java - Build from Scratch

Intersection Point of Two Linked Lists

📖 Scenario: Imagine two train tracks that merge into one track at some point. We want to find the exact point where the two tracks join. In programming, this is like finding the intersection point of two linked lists.

🎯 Goal: You will build a Java program to find the intersection point of two singly linked lists. The program will create two linked lists that share some nodes, then find and print the value at the intersection node.

📋 What You'll Learn

Create two linked lists with some shared nodes

Use a helper variable to store the length difference of the lists

Implement logic to find the intersection node by aligning the lists

Print the value of the intersection node or -1 if no intersection

💡 Why This Matters

🌍 Real World

Finding intersection points is useful in network routing, version control systems, and merging data streams where two paths join.

💼 Career

Understanding linked list intersections helps in technical interviews and solving problems related to memory management and data structure optimization.

1

Create two linked lists with shared nodes

Create a class called Node with an integer data and a Node next. Then create two linked lists: head1 with nodes 3 -> 6 -> 9 -> 15 -> 30, and head2 with nodes 10 -> 15 -> 30, where nodes 15 and 30 are shared nodes between the two lists.

DSA Java

// Define Node class and create two linked lists with shared nodes
// Your code here

Hint

Start by defining the Node class. Then create the first list nodes 3, 6, 9. Create shared nodes 15 and 30. Attach shared nodes to the first list. Create second list starting with 10 and link it to the shared nodes.

2

Calculate lengths and difference

Add a method getLength(Node head) that returns the length of a linked list. Then create two integer variables len1 and len2 to store lengths of head1 and head2. Finally, create an integer diff that stores the absolute difference between len1 and len2.

DSA Java

class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class Main {
    public static int getLength(Node head) {
        // Your code here
    }

    public static void main(String[] args) {
        Node head1 = new Node(3);
        head1.next = new Node(6);
        head1.next.next = new Node(9);
        Node shared1 = new Node(15);
        Node shared2 = new Node(30);
        shared1.next = shared2;
        head1.next.next.next = shared1;

        Node head2 = new Node(10);
        head2.next = shared1;

        // Calculate lengths and difference
        // Your code here
    }
}

Hint

Use a while loop to count nodes in getLength. Then call this method for both lists and find the absolute difference.

3

Find the intersection node

Write a method getIntersectionNode(Node head1, Node head2, int diff) that returns the intersection Node. Inside, move the pointer of the longer list ahead by diff nodes. Then move both pointers one by one until they meet or reach null. Return the intersection node or null if none.

DSA Java

class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class Main {
    public static int getLength(Node head) {
        int length = 0;
        Node current = head;
        while (current != null) {
            length++;
            current = current.next;
        }
        return length;
    }

    public static Node getIntersectionNode(Node head1, Node head2, int diff) {
        // Your code here
    }

    public static void main(String[] args) {
        Node head1 = new Node(3);
        head1.next = new Node(6);
        head1.next.next = new Node(9);
        Node shared1 = new Node(15);
        Node shared2 = new Node(30);
        shared1.next = shared2;
        head1.next.next.next = shared1;

        Node head2 = new Node(10);
        head2.next = shared1;

        int len1 = getLength(head1);
        int len2 = getLength(head2);
        int diff = Math.abs(len1 - len2);

        // Call getIntersectionNode
        // Your code here
    }
}

Hint

Move the longer list pointer ahead by diff. Then move both pointers together until they meet or reach the end.

4

Print the intersection node data

Add a print statement in main to display the data of the intersection node if it exists, otherwise print -1.

DSA Java

class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class Main {
    public static int getLength(Node head) {
        int length = 0;
        Node current = head;
        while (current != null) {
            length++;
            current = current.next;
        }
        return length;
    }

    public static Node getIntersectionNode(Node head1, Node head2, int diff) {
        Node longer = head1;
        Node shorter = head2;
        if (getLength(head2) > getLength(head1)) {
            longer = head2;
            shorter = head1;
        }

        for (int i = 0; i < diff; i++) {
            if (longer == null) return null;
            longer = longer.next;
        }

        while (longer != null && shorter != null) {
            if (longer == shorter) {
                return longer;
            }
            longer = longer.next;
            shorter = shorter.next;
        }
        return null;
    }

    public static void main(String[] args) {
        Node head1 = new Node(3);
        head1.next = new Node(6);
        head1.next.next = new Node(9);
        Node shared1 = new Node(15);
        Node shared2 = new Node(30);
        shared1.next = shared2;
        head1.next.next.next = shared1;

        Node head2 = new Node(10);
        head2.next = shared1;

        int len1 = getLength(head1);
        int len2 = getLength(head2);
        int diff = Math.abs(len1 - len2);

        Node intersection = getIntersectionNode(head1, head2, diff);

        // Print intersection data or -1
        // Your code here
    }
}

Hint

Check if intersection is not null. If yes, print intersection.data. Otherwise, print -1.

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