Intersection Point of Two Linked Lists

Problem Statement

Given the heads of two singly linked lists, find the node at which the two lists intersect. If the two linked lists have no intersection, return null.

Note: The lists are guaranteed to have no cycles, and the original structure of the lists must be preserved.

Example

Input: List A: 1 -> 2 -> 3 ↘ 7 -> 8 -> 9 -> null ↗ List B: 4 -> 5 Output: Node with value 7 Input: List A: 1 -> 2 -> 3 -> null List B: 4 -> 5 -> 6 -> null Output: null (no intersection)

---

Brute Force Approach (Nested Loops)

Intuition

For each node in list A, check if it exists in list B by traversing list B completely. The first common node is the intersection point.

Algorithm

1. For each node in list A
2. Traverse list B and check if any node matches
3. If found, return that node
4. If no match found, return null

Implementation

Complexity Analysis

• Time Complexity: O(m * n) - Nested traversal
• Space Complexity: O(1) - No extra space

---

Better Approach (Using HashSet)

Intuition

Store all nodes of one list in a hash set. Then traverse the other list and check if any node exists in the set.

Algorithm

1. Add all nodes of list A to a hash set
2. Traverse list B
3. For each node in B, check if it's in the set
4. First match is the intersection point

Implementation

Complexity Analysis

• Time Complexity: O(m + n) - Traverse both lists once
• Space Complexity: O(m) or O(n) - Store one list in set

---

Optimal Approach 1 (Length Difference)

Intuition

If we align both lists by their ends (since intersection means shared tail), we can find the intersection. Calculate the length difference and advance the longer list's pointer by that difference, then move both pointers together.

Algorithm

1. Calculate lengths of both lists
2. Find the difference in lengths
3. Advance the longer list's pointer by the difference
4. Move both pointers together until they meet

Visualization

List A: 1 -> 2 -> 3 -> 7 -> 8 -> 9 (length 6) ↑ List B: 4 -> 5 -> 7 -> 8 -> 9 (length 5) Difference = 6 - 5 = 1 Advance A by 1: A: 2 -> 3 -> 7 -> 8 -> 9 ↑ B: 4 -> 5 -> 7 -> 8 -> 9 ↑ Move together until they meet at node 7

Implementation

Complexity Analysis

• Time Complexity: O(m + n) - Traverse both lists
• Space Complexity: O(1) - Only using pointers

---

Optimal Approach 2 (Two Pointer Trick)

Intuition

This elegant approach uses the fact that a + c + b = b + c + a, where:

• a = length of list A before intersection
• b = length of list B before intersection
• c = length of common part

Both pointers traverse the same total distance before meeting.

Algorithm

1. Start two pointers at heads of both lists
2. When a pointer reaches the end, redirect it to the head of the other list
3. They will meet at the intersection (or both reach null)

Visualization

A: 1 -> 2 -> 3 -> 7 -> 8 (a=3, c=2) ↑ B: 4 -> 5 -> 7 -> 8 (b=2, c=2) Pointer pA: 1 -> 2 -> 3 -> 7 -> 8 -> 4 -> 5 -> 7 Pointer pB: 4 -> 5 -> 7 -> 8 -> 1 -> 2 -> 3 -> 7 ↑ Both meet here! pA travels: a + c + b = 3 + 2 + 2 = 7 pB travels: b + c + a = 2 + 2 + 3 = 7

Implementation

Complexity Analysis

• Time Complexity: O(m + n) - Each pointer traverses both lists once
• Space Complexity: O(1) - Only using two pointers

---

Comparison of Approaches

| Approach | Time | Space | Notes | |----------|------|-------|-------| | Brute Force | O(m*n) | O(1) | Simple but slow | | HashSet | O(m+n) | O(m) | Extra space needed | | Length Difference | O(m+n) | O(1) | Two passes | | Two Pointer Trick | O(m+n) | O(1) | Most elegant |

---

Key Takeaways

1. The two pointer trick is the most elegant solution
2. The key insight is that a + c + b = b + c + a
3. If there's no intersection, both pointers become null together after two passes
4. This problem tests understanding of linked list structure and pointer manipulation
5. Compare node references, not values - two nodes with same value are different nodes
6. This is a classic interview problem (LeetCode #160)