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.