Detect intersection of two linked lists
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given two singly linked lists that may converge to share a common tail, determine whether they intersect and return the first node at which they join. Nodes are compared by reference, not by value. Aim for O(m+n) time and O(
1) extra space. Describe and implement an approach, justify its correctness, and analyze time and space complexity. Discuss edge cases such as one empty list, no intersection, and very unequal lengths.
Quick Answer: This question evaluates a candidate's ability to manipulate singly linked lists, reason about pointer and reference equality between nodes, and perform algorithmic analysis of time and space trade-offs.
Two singly linked lists may converge and share a common tail. Two nodes are considered the same only when they are the same node by reference (identity), never merely by equal value. Determine whether the two lists intersect and return the value of the first node at which they join, or report no intersection.
Because raw pointer-based linked lists cannot be passed directly to your function, the two lists are described by three value arrays:
- prefixA: the values of the nodes that are unique to list A (its prefix before the intersection).
- prefixB: the values of the nodes that are unique to list B (its prefix before the intersection).
- sharedTail: the values of the shared suffix, i.e. the intersection node and everything after it. The SAME physical nodes are appended to the end of both prefixes. An empty sharedTail means the two lists do NOT intersect (each list is just its own prefix, ending in null).
Reconstruct the two lists from these arrays (appending the same shared-tail node objects to both prefixes), then return the value of the first shared node, or null/None if the lists do not intersect.
Aim for O(m + n) time and O(1) extra space, where m and n are the list lengths. Note that comparing by value would be incorrect (the equal-value, non-intersecting example demonstrates why); you must compare by node identity.
Classic two-pointer idea: advance one pointer through each list; when a pointer reaches the end, redirect it to the head of the other list. After at most m + n steps both pointers have traversed prefixA + sharedTail + prefixB (and symmetrically), so they meet at the first shared node if one exists, or both reach null simultaneously if not.
Constraints
- 0 <= len(prefixA), len(prefixB) <= 30000
- 0 <= len(sharedTail) <= 30000
- An empty sharedTail means the two lists do not intersect.
- Node values fit in a 32-bit signed integer.
- Nodes are compared by reference (identity), not by value.
- Target O(m + n) time and O(1) extra space.
Examples
Input: ([1, 2, 3], [6, 7], [4, 5])
Expected Output: 4
Explanation: List A is 1->2->3->4->5 and list B is 6->7->4->5; they merge at the node with value 4, which is the first shared node.
Input: ([1, 9, 1], [3], [2, 4])
Expected Output: 2
Explanation: List A is 1->9->1->2->4 and list B is 3->2->4; the shared tail starts at value 2, so the first intersection node is 2.
Hints
- Comparing nodes by value is wrong: two lists can contain identical values yet never share a physical node. You must compare by node identity.
- If the lists have lengths m and n, the part after the intersection has the same length for both. The difference m - n comes entirely from the unique prefixes.
- Two-pointer trick: walk pointer A through list A then continue into list B, and pointer B through list B then into list A. Both travel m + n steps, so they align at the first shared node — or both hit null together when there is no intersection.
- Handle the empty-list case first: if either reconstructed list is empty, there can be no intersection.