LeetCode 160: Intersection of Two Linked Lists Solution in Python Explained

Problem Statement

In LeetCode 160, you’re given two singly linked list heads, headA and headB. The lists may intersect at a node (sharing a common tail), and your task is to return that intersection node, or null if no intersection exists. The intersection is defined by reference (same node object), not value, and you should aim for O(n) time and O(1) space complexity. This differs from substring analysis like LeetCode 159: Longest Substring with At Most Two Distinct Characters, focusing on linked list traversal rather than string processing.

Constraints

• Number of nodes in each list: 1 <= n, m <= 3 * 10^4
• Node values: 1 <= Node.val <= 10^5
• Intersection at a node or no intersection (null)

Example

Let’s see some cases:

Copy codeInput: headA = [4,1,8,4,5], headB = [5,6,1,8,4,5], intersectVal = 8
      4 -> 1 -> 8 -> 4 -> 5
            /
5 -> 6 -> 1
Output: Node 8
Explanation: Lists intersect at node with value 8.

Copy codeInput: headA = [1,9,1,2,4], headB = [3,2,4], intersectVal = 2
      1 -> 9 -> 1 -> 2 -> 4
                 /
3 -> 2
Output: Node 2
Explanation: Intersection at node with value 2.

Copy codeInput: headA = [2,6,4], headB = [1,5], intersectVal = 0
      2 -> 6 -> 4
1 -> 5
Output: null
Explanation: No intersection.

These examples show we’re finding a shared node by reference.

Understanding the Problem

How do you solve LeetCode 160: Intersection of Two Linked Lists in Python? Take headA = [4,1,8,4,5], headB = [5,6,1,8,4,5], intersecting at node 8. The lists converge at this node, sharing the tail [8,4,5]. For [1,9,1,2,4] and [3,2,4], intersection is at 2. If no intersection, return null. We need O(n) time and O(1) space, ruling out naive length counting without alignment. This isn’t a file reading task like LeetCode 158: Read N Characters Given Read4 II; it’s about linked list convergence. We’ll use: 1. Two-Pointer Length Alignment: O(n) time, O(1) space—our best solution. 2. Hash Set with Node Tracking: O(n) time, O(n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Two-Pointer Length Alignment Approach

Explanation

Two-Pointer Length Alignment uses two pointers to traverse both lists, aligning their lengths implicitly:

• Start pointers pA and pB at headA and headB.
• Traverse until null; when one reaches the end, redirect it to the other list’s head.
• Continue until they meet (at the intersection or null).

This works because the total distance (lengthA + lengthB) is the same for both pointers, and the intersection node aligns their paths. It’s the best solution due to its O(n) time complexity (where n is the total nodes), O(1) space usage (no extra structures), and elegant simplicity.

For [4,1,8,4,5] and [5,6,1,8,4,5]:

• pA: 4→1→8→4→5→5→6→1→8.
• pB: 5→6→1→8→4→5→4→1→8.
• Meet at 8.

Step-by-Step Example

Assume a ListNode class: class ListNode: def __init__(self, x): self.val = x; self.next = None.

Example 1: headA = [4,1,8,4,5], headB = [5,6,1,8,4,5], intersect at 8

Goal: Return Node 8.

• Start: pA = 4, pB = 5.
• Step 1: pA = 1, pB = 6.
• Step 2: pA = 8, pB = 1.
• Step 3: pA = 4, pB = 8.
• Step 4: pA = 5, pB = 4.
• Step 5: pA = null, pB = 5, redirect pA = 5, pB = null, redirect pB = 4.
• Step 6: pA = 6, pB = 1.
• Step 7: pA = 1, pB = 8.
• Step 8: pA = 8, pB = 4, meet at 8.
• Finish: Return Node 8.

Example 2: headA = [1,9,1,2,4], headB = [3,2,4], intersect at 2

Goal: Return Node 2.

• Start: pA = 1, pB = 3.
• Step 1: pA = 9, pB = 2.
• Step 2: pA = 1, pB = 4.
• Step 3: pA = 2, pB = null, redirect pB = 1.
• Step 4: pA = 4, pB = 9.
• Step 5: pA = null, pB = 1, redirect pA = 3.
• Step 6: pA = 2, pB = 2, meet at 2.
• Finish: Return Node 2.

Example 3: headA = [2,6,4], headB = [1,5], no intersection

Goal: Return null.

• Start: pA = 2, pB = 1.
• Step 1: pA = 6, pB = 5.
• Step 2: pA = 4, pB = null, pB = 2.
• Step 3: pA = null, pB = 6, pA = 1.
• Step 4: pA = 5, pB = 4.
• Step 5: pA = null, pB = null, both null.
• Finish: Return null.

How the Code Works (Two-Pointer Length Alignment) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codeclass ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    # Line 1: Handle null cases
    if not headA or not headB:
        # If either list is empty (e.g., []), no intersection
        return None

    # Line 2: Initialize pointers
    pA = headA
    # Pointer for list A (e.g., 4)
    pB = headB
    # Pointer for list B (e.g., 5)

    # Line 3: Traverse lists with redirection
    while pA != pB:
        # Continue until pointers meet (e.g., at 8 or null)

        # Line 4: Move pointers
        pA = pA.next
        # Advance A (e.g., 4→1)
        pB = pB.next
        # Advance B (e.g., 5→6)

        # Line 5: Redirect to other head if null
        if not pA:
            # If A reaches end (e.g., null after 5)
            pA = headB
            # Redirect to B’s head (e.g., 5)
        if not pB:
            # If B reaches end (e.g., null after 4)
            pB = headA
            # Redirect to A’s head (e.g., 4)

    # Line 6: Return intersection node
    return pA
    # Meeting point (e.g., Node 8 or null)

This detailed breakdown clarifies how two-pointer length alignment efficiently finds the intersection.

Alternative: Hash Set with Node Tracking Approach

Explanation

Hash Set with Node Tracking stores nodes from one list in a set, then checks the other list for matches:

• Traverse headA, adding nodes to a set.
• Traverse headB, checking for the first node in the set.
• Return the intersection or null.

It’s a practical alternative, O(n) time with O(n) space (set size), but uses extra space, less optimal than the two-pointer method.

For [4,1,8,4,5] and [5,6,1,8,4,5]:

• Set: {4,1,8,4,5{.
• Check 5,6,1→8 matches.

Step-by-Step Example (Alternative)

For [1,9,1,2,4] and [3,2,4]:

• Step 1: Set = {1,9,1,2,4{.
• Step 2: Check 3→no, 2→yes, return 2.
• Finish: Return Node 2.

How the Code Works (Hash Set)

Copy codedef getIntersectionNodeHash(headA: ListNode, headB: ListNode) -> ListNode:
    if not headA or not headB:
        return None
    node_set = set()
    curr = headA
    while curr:
        node_set.add(curr)
        curr = curr.next
    curr = headB
    while curr:
        if curr in node_set:
            return curr
        curr = curr.next
    return None

Complexity

• Two-Pointer Length Alignment:
• Time: O(n) – total nodes traversed.
• Space: O(1) – constant space.
• Hash Set with Node Tracking:
• Time: O(n) – two passes.
• Space: O(n) – set size.

Efficiency Notes

Two-Pointer Length Alignment is the best solution with O(n) time and O(1) space, meeting the problem’s optimal constraints—Hash Set with Node Tracking matches time complexity but uses O(n) space, making it simpler but less space-efficient.

Key Insights

• Alignment: Equalizes path lengths.
• Hash Set: Tracks nodes explicitly.
• Intersection: Shared reference.

Additional Example

For headA = [1,2], headB = [3,1,2]:

• Goal: Node 1.
• Two-Pointer: Meet at 1.

Edge Cases

• No Intersection: [1], [2] → null.
• Single Node: [1], [1] → Node 1.
• Different Lengths: Handled by alignment.

Both solutions handle these well.

Final Thoughts

LeetCode 160: Intersection of Two Linked Lists in Python is a clever linked list challenge. The Two-Pointer Length Alignment solution excels with its efficiency and minimalism, while Hash Set with Node Tracking offers an intuitive approach. Want more? Try LeetCode 141: Linked List Cycle for cycle detection or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 160 on LeetCode with [4,1,8,4,5] and [5,6,1,8,4,5], aiming for Node 8—test your skills now!