💬 Discord
Sign In
NeetCode #310LC-160EasyLinked List
← Back to All Problems

#310 · #160 · Intersection of Two Linked Lists(相交链表)

📌 Problem Statement & Constraints

Given the heads of two singly linked lists headA and headB, return the node at which they intersect, or null if they do not. The lists may have different lengths. Constraints: the number of nodes is in [1, 10^5]. The follow-up asks for O(1) memory.

💡 Core Algorithmic Approaches

  1. Two-pointer switching: advance both pointers; when one reaches the end, redirect it to the other list's head.
  2. After at most lenA + lenB steps, both pointers have travelled the same total distance, so they either meet at the intersection or both become None simultaneously.
  3. This elegantly equalises the length difference without computing lengths explicitly.
  4. An alternative computes both lengths, advances the longer list's pointer by the difference, then walks in lockstep.

💻 Benchmark Python3 Implementation

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        a, b = headA, headB
        while a is not b:                  # identity, not value equality
            a = a.next if a else headB     # switch to the other list at the end
            b = b.next if b else headA
        return a                           # None if no intersection


# Length-difference variant: explicit but equally O(1) space
class Solution2:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        def length(node):
            n = 0
            while node:
                n += 1
                node = node.next
            return n

        la, lb = length(headA), length(headB)
        a, b = headA, headB
        for _ in range(la - lb if la > lb else 0):
            a = a.next
        for _ in range(lb - la if lb > la else 0):
            b = b.next
        while a is not b:
            a = a.next
            b = b.next
        return a

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m + n): each pointer traverses at most both lists once.
💾 Space Complexity
O(1): two pointers.

⚠️ Interview Pitfalls & Follow-ups

  • Comparing a.val == b.val: nodes are identified by reference, and two distinct nodes may hold equal values.
  • Using a hash set of nodes: O(m) space, which the follow-up forbids.
  • Not handling the no-intersection case: both pointers become None at the same time, and the loop exits returning None -- correct, provided the a is not b comparison is used (not !=, which would be equivalent for objects but is better written as identity).
  • Switching pointers more than once: the loop handles it naturally, but the logic depends on switching exactly at the end of each traversal.