Given the heads of two singly linked lists, headA and headB, return the node where the two lists merge (the first node they share), or null if they never meet. The lists have no cycles and must keep their structure. In the tests, intersectVal is the value of the shared node (0 if none) and skipA / skipB are how many nodes of each list come before it; these are only used to build the lists. The judge shows the value of the node you return.
- Each list has 1 to 3 * 10^4 nodes
- 1 <= Node.val <= 10^5
- There are no cycles
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force checks every node of A against every node of B, O(m * n), and the hash set version is O(m + n) time but O(m) space. To use O(1) space, note that the two lists only differ in the part before the merge. If pointer a walks A and then B, and pointer b walks B and then A, both cover lenA + lenB nodes in total. After switching lists they are lined up at the same distance from the shared tail, so they reach the intersection at the same moment. If there is no intersection, they both become null at the same time and the loop ends.
Algorithm
- Set
a = headAandb = headB. - While
a != b: moveatoa.next, or toheadBifais null. - In the same loop, move
btob.next, or toheadAifbis null. - Return
a(the shared node, or null).
O(m + n)Space: O(1)class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]: a, b = headA, headB # each pointer walks its own list, then the other: both cover lenA + lenB while a is not b: a = headB if a is None else a.next b = headA if b is None else b.next return a # shared node, or None if none