What is the time complexity to locate the intersection node of two singly linked lists using a length-alignment approach (assuming they intersect)?

• A. O(n) time and O(1) space
• B. O(m) time
• C. O(1) time
• D. O(m+n) time to find the intersection node using length alignment

Answer: (D)

The idea behind length alignment is to equalize the distance to the end from both lists, so once you start comparing nodes in lockstep you’ll meet at the intersection if one exists. To do that, you first need to know how long each list is, which means you traverse both lists once each. That costs m + n steps. Then you skip the extra nodes in the longer list by the difference |m − n|, adding at most |m − n| steps. After that, you walk both pointers together until you reach the intersection, which takes at most min(m, n) steps. In total that’s (m + n) + |m − n| + min(m, n), which simplifies to a bound proportional to m + n. So the time complexity is O(m + n). This approach uses only a few pointers, so the space cost is O(1).