Intersection of Two Linked Lists
Given the heads of two singly linked lists, return the node at which the two lists intersect. Solve in $O(m+n)$ time and $O(1)$ extra memory.
Why Interviewers Ask This
Apple interviewers ask this to evaluate a candidate's ability to manipulate pointers without allocating extra memory. They specifically test if you can solve complex traversal problems using the two-pointer technique, demonstrating deep understanding of linked list mechanics and efficient algorithmic thinking under strict space constraints.
How to Answer This Question
1. Clarify Requirements: Confirm if lists are singly linked, if they contain cycles, and verify the O(m+n) time and O(1) space constraints explicitly.
2. Analyze Constraints: Acknowledge that hash maps are forbidden due to space limits, forcing a pointer-based solution.
3. Propose Strategy: Suggest the two-pointer approach where each pointer traverses its own list then switches to the other head. Explain how this equalizes path lengths, ensuring both pointers meet at the intersection or null simultaneously.
4. Walk Through Example: Trace the logic with specific node counts (e.g., List A has 3 unique nodes, List B has 5) to show how the pointers cross over.
5. Implement & Verify: Write clean code handling edge cases like no intersection, different starting lengths, and empty lists while emphasizing constant space usage.
Key Points to Cover
- Explicitly state the O(1) space constraint as the primary driver for the chosen algorithm
- Demonstrate the 'cross-over' logic where pointers switch heads to equalize path lengths
- Correctly handle the case where no intersection exists by returning null when both pointers are null
- Avoid calculating list lengths first, as that adds unnecessary passes or requires extra variables
- Show clear understanding of pointer manipulation rather than relying on hash sets
Sample Answer
To solve this efficiently within Apple's strict performance standards, I will use the two-pointer technique. First, I initialize two pointers, pA and pB, at the heads of list A and list B respectively. The core insight is that if we traverse both lists sequentially, switching to the other list's head upon reaching the end, both pointers will travel the exact same total distance by the time they reach the intersection point. Specifically, pA travels length A plus length B, and pB travels length B plus length A. If an intersection exists, they will meet there. If not, they will both eventually become null after traversing both lists completely, correctly returning null. This approach guarantees O(m+n) time complexity because we visit each node at most twice, and O(1) space since we only store two pointers regardless of input size. For example, if list A has 3 unique nodes before a shared tail of 2 nodes, and list B has 5 unique nodes before that same tail, pA will traverse 3 + 7 = 10 steps, and pB will traverse 5 + 7 = 12 steps? No, wait, let me correct that trace: pA goes 3 unique + 2 shared + 5 unique from B = 10 steps. pB goes 5 unique + 2 shared + 3 unique from A = 10 steps. They align perfectly at the intersection node. This method elegantly handles lists of different lengths without calculating lengths beforehand, which is crucial for maintaining constant space.
Common Mistakes to Avoid
- Using a HashSet to store visited nodes, which violates the O(1) space requirement
- Calculating the difference in list lengths and skipping nodes manually, adding unnecessary complexity
- Failing to handle the scenario where lists do not intersect, leading to infinite loops or incorrect returns
- Confusing node identity with value equality, assuming values match means they intersect
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.