Insertion of two Linked Lists

Problem Link

160. Intersection of Two Linked Lists – LeetCode

Problem Statement

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, return null.

The intersection is defined by reference (i.e., the same node object), not by value.

Examples

Example 1:

Input:
ListA: 4 → 1 → 8 → 4 → 5
ListB: 5 → 6 → 1 → 8 → 4 → 5

Output: Intersected at '8'

Example 2:

Input:
ListA: 1 → 9 → 1 → 2 → 4
ListB: 3 → 2 → 4

Output: Intersected at '2'

Example 3:

Input:
ListA: 2 → 6 → 4
ListB: 1 → 5

Output: null (No intersection)

Constraints

• The number of nodes in each list is in the range [0, 10⁴]

• 1 <= Node.val <= 10⁵

• The lists may or may not intersect

• Intersection is based on node reference, not node value

Intuition

If the two linked lists intersect, they must share a common tail.

If we traverse both lists and switch heads once we reach the end, then after one complete loop, both pointers will be equal distance from the intersection point, if it exists.

This elegant trick ensures both pointers traverse equal total lengths regardless of original list length differences.

Approach: Two Pointer Technique with Head Switch

1. Initialize two pointers a and b at headA and headB.

2. Traverse both lists:

   • If a reaches the end, redirect it to headB

   • If b reaches the end, redirect it to headA

   • If they intersect, a == b will eventually point to the intersection node

3. If there is no intersection, both pointers will reach null at the same time.

Java Code

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;

        ListNode a = headA;
        ListNode b = headB;

        while (a != b) {
            a = (a == null) ? headB : a.next;
            b = (b == null) ? headA : b.next;
        }

        return a; // either the intersection node or null
    }
}

Time and Space Complexity

Dry Run

Input:

headA = [4,1,8,4,5]
headB = [5,6,1,8,4,5]
Intersection at node with value 8

Steps:

• a = 4, b = 5 → not equal

• a = 1, b = 6 → not equal

• ...

• a = null → reset to headB

• b = null → reset to headA

• Eventually: a = 8, b = 8 → match → return intersection

Alternate Approach (Using Lengths)

1. Compute lengths of both lists.

2. Advance the longer list's head by the length difference.

3. Move both heads in parallel until they match or reach null.

Time: O(n + m)
Space: O(1)

Conclusion

This problem is a brilliant use of pointer manipulation and highlights how clever switching can equalize pointer distances.

Mastering this technique is useful in many advanced linked list problems involving cycles, merges, and overlaps.