Intersection Point of Two Linked Lists in DSA Java - Execution Trace

Concept Flow - Intersection Point of Two Linked Lists

Start at head of List1 and List2

↓

Traverse both lists simultaneously

↓

If nodes are same (by reference)?

Yes→Intersection found

No↓

Move pointer to next node

↓

If end reached in one list?

↓

Switch pointer to head of other list

↓

Repeat traversal until pointers meet or both null

↓

Return intersection node or null

Traverse both lists with two pointers, switching heads when reaching end, to find the intersection node by reference or return null if none.

Execution Sample

DSA Java

Node getIntersection(Node headA, Node headB) {
  Node pA = headA, pB = headB;
  while (pA != pB) {
    pA = (pA == null) ? headB : pA.next;
    pB = (pB == null) ? headA : pB.next;
  }
  return pA;
}

This code finds the intersection node of two linked lists by traversing them with two pointers that switch heads when reaching the end.

Execution Table

Step	Operation	Pointer pA	Pointer pB	Visual State (List1 & List2 nodes)	Notes
1	Initialize pointers	Node1A	Node1B	List1: 1A->2A->3C->4C->5C->null List2: 1B->2B->3C->4C->5C->null	pA at headA, pB at headB
2	Compare pA and pB	Node1A	Node1B	Same? No	Move both pointers
3	Move pA and pB	Node2A	Node2B	pA->2A, pB->2B
4	Compare pA and pB	Node2A	Node2B	Same? No	Move both pointers
5	Move pA and pB	Node3C	Node3C	pA->3C, pB->3C
6	Compare pA and pB	Node3C	Node3C	Same? Yes	Intersection found at Node3C
7	Return intersection	Node3C	Node3C	Return Node3C	End

💡 Pointers pA and pB meet at Node3C, the intersection point.

Variable Tracker

Variable	Start	After Step 3	After Step 5	Final
pA	Node1A	Node2A	Node3C	Node3C
pB	Node1B	Node2B	Node3C	Node3C

Key Moments - 3 Insights

Why do we switch pointer to the other list's head when reaching the end?

Switching pointers ensures both traverse equal total length, aligning them to meet at intersection or null, as seen in steps 3 and 5 where pointers move forward and switch lists if needed.

Why do we compare nodes by reference, not by value?

Intersection means the exact same node object, not just same value. The execution_table shows pointers meeting at Node3C by reference, confirming intersection.

What happens if there is no intersection?

Both pointers eventually become null after traversing both lists fully, causing the loop to exit and return null, meaning no intersection found.

Visual Quiz - 3 Questions

Look at the execution table, what node is pointer pA at after step 3?

A Node1B

B Node2A

C Node3C

D Node1A

💡 Hint

Check the 'Pointer pA' column in row for step 3.

At which step do pointers pA and pB first point to the same node?

A Step 5

B Step 2

C Step 6

D Step 4

💡 Hint

Look for the first 'Same? Yes' in the 'Notes' column.

If the lists had no intersection, what would happen to pointers pA and pB?

A They would meet at a node with same value

B They would loop infinitely

C They would both become null after traversing both lists

D They would stop at the longer list's end

💡 Hint

Refer to the 'key_moments' explanation about no intersection scenario.

Concept Snapshot

Intersection Point of Two Linked Lists:
- Use two pointers starting at heads of each list.
- Move pointers forward one node at a time.
- When a pointer reaches end, switch it to the other list's head.
- Continue until pointers meet (intersection) or both null (no intersection).
- Compare nodes by reference, not value.

Full Transcript

To find the intersection point of two linked lists, we use two pointers starting at the heads of each list. We move both pointers forward one node at a time. When a pointer reaches the end of its list, we switch it to the head of the other list. This way, both pointers traverse equal total length. We compare the nodes by reference, not by value. When the pointers meet, that node is the intersection point. If they both become null, there is no intersection. This method ensures we find the intersection efficiently without extra space.

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