How to Solve: Intersection of Two Linked Lists

How to Solve: Intersection of Two Linked Lists

(Complete Guide for FAANG-Level Interviews)

? Introduction

"This problem tests your ability to optimize space and time—nail it, and you prove you can handle real-world constraints like memory limits and edge cases in under 30 minutes."

? WHAT YOU NEED TO KNOW FIRST

1. Linked List Traversal – Must be comfortable moving pointers (current = current.next).
2. Two-Pointer Technique – Used to traverse two sequences at different speeds.
3. Cycle Detection (Optional) – Helps in advanced follow-ups (e.g., detecting cycles before finding intersection).

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

(Repeatable mental checklist for every linked list intersection problem.)

1. Clarify Constraints
2. Are the lists guaranteed to intersect? (If not, handle null case.)
3. Can we modify the lists? (If not, avoid hash sets.)

4. Are cycles possible? (If yes, use Floyd’s first.)

5. Compute Lengths

6. Traverse both lists to get lengths lenA and lenB.

7. If lengths differ, skip extra nodes in the longer list.

8. Align Pointers

9. Move the pointer of the longer list forward by |lenA - lenB| nodes.

10. Now both pointers are equidistant from the end.

11. Traverse in Sync

12. Move both pointers one node at a time.
13. If they meet, return the node (intersection found).

14. If either reaches null, return null (no intersection).

15. Edge Cases

16. One or both lists are empty.
17. Lists are identical (intersection at head).

18. No intersection (return null).

19. Optimize for Follow-Ups

20. If cycles are possible, detect them first (Floyd’s algorithm).
21. If space is allowed, use a hash set for O(n) time.

? WORKED EXAMPLES

Example 1 – Basic (No Cycles, Optimal Space)

Problem: Given two singly linked lists, return the node where they intersect (or null if no intersection).

Solution (Two-Pointer Technique):

def getIntersectionNode(headA, headB):

    # Step 1: Compute lengths

    lenA, lenB = 0, 0

    currA, currB = headA, headB

    while currA:

        lenA += 1

        currA = currA.next

    while currB:

        lenB += 1

        currB = currB.next


    # Step 2: Align pointers

    currA, currB = headA, headB

    if lenA > lenB:

        for _ in range(lenA - lenB):

            currA = currA.next

    else:

        for _ in range(lenB - lenA):

            currB = currB.next


    # Step 3: Traverse in sync

    while currA and currB:

        if currA == currB:

            return currA

        currA = currA.next

        currB = currB.next

    return None

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

Why This Works: - By aligning pointers, we ensure both traverse the same number of nodes before reaching the end. - If they intersect, they must meet at the intersection node.

Example 2 – Medium (With Cycles)

Problem: Find the intersection node of two linked lists that may contain cycles.

Solution (Floyd’s + Two-Pointer):

def getIntersectionNodeWithCycle(headA, headB):

    # Step 1: Detect cycles (Floyd's algorithm)

    def detectCycle(head):

        slow = fast = head

        while fast and fast.next:

            slow = slow.next

            fast = fast.next.next

            if slow == fast:

                return slow  # Cycle detected

        return None


    cycleA = detectCycle(headA)

    cycleB = detectCycle(headB)


    # Case 1: No cycles (use standard two-pointer)

    if not cycleA and not cycleB:

        return getIntersectionNode(headA, headB)


    # Case 2: One list has a cycle, the other doesn't (no intersection)

    if (cycleA and not cycleB) or (cycleB and not cycleA):

        return None


    # Case 3: Both have cycles (check if cycles are the same)

    # Traverse cycleA to see if cycleB is reachable

    temp = cycleA.next

    while temp != cycleA:

        if temp == cycleB:

            break

        temp = temp.next

    if temp != cycleB:

        return None  # Different cycles, no intersection


    # Now find intersection (same as standard two-pointer)

    lenA, lenB = 0, 0

    currA, currB = headA, headB

    while currA != cycleA:

        lenA += 1

        currA = currA.next

    while currB != cycleB:

        lenB += 1

        currB = currB.next


    currA, currB = headA, headB

    if lenA > lenB:

        for _ in range(lenA - lenB):

            currA = currA.next

    else:

        for _ in range(lenB - lenA):

            currB = currB.next


    while currA != cycleA and currB != cycleB:

        if currA == currB:

            return currA

        currA = currA.next

        currB = currB.next

    return cycleA  # Intersection is the cycle start

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

Why This Works: - First detect cycles (if any). - If both lists have cycles, check if they share the same cycle. - If they do, find the intersection before the cycle starts.

Example 3 – Hard (Follow-Up: Find Intersection Without Lengths)

Problem: Find the intersection node without computing lengths (optimized two-pointer).

Solution (Two-Pointer Swap):

def getIntersectionNodeOptimized(headA, headB):

    if not headA or not headB:

        return None


    ptrA, ptrB = headA, headB


    while ptrA != ptrB:

        ptrA = ptrA.next if ptrA else headB

        ptrB = ptrB.next if ptrB else headA


    return ptrA

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

Why This Works: - Pointers traverse both lists, swapping to the other list’s head when they reach the end. - They meet at the intersection after traversing lenA + lenB nodes.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Alright, let’s lock this in. For linked list intersection problems, here’s your battle plan:

1. Clarify constraints – Are cycles possible? Can we modify the lists?
2. Compute lengths – Traverse both lists to find their lengths.
3. Align pointers – Skip extra nodes in the longer list.
4. Traverse in sync – Move both pointers until they meet (or hit null).
5. Handle edge cases – Empty lists, identical lists, no intersection.

For follow-ups, remember: - No lengths? Use the two-pointer swap trick. - Cycles? Detect them first with Floyd’s algorithm.

You’ve got this. Now go crush that interview!

Final Notes

• Practice: Implement all three solutions (basic, cycle, optimized) on a whiteboard.
• Time Yourself: Aim for <15 minutes per solution in mock interviews.
• Test Edge Cases: Empty lists, identical lists, no intersection, cycles.

This framework ensures you never panic when this problem appears. Good luck! ?