ListNode(val, next=None) is in the starter. Keep it.
Two singly linked lists start at head_a and head_b. They may merge: from some node on, both lists run through the very same node objects to the same end, like two roads joining into one. Neither list loops. Write get_intersection_node(head_a, head_b) that returns the first shared node, or None if the lists never meet.
head_a: 4 -> 1 -> 9 -> 3 -> 5
head_b: 6 -> 1 -> 2 -> 9 -> 3 -> 5 (9, 3 and 5 are the same nodes in both)
returns the node with value 9
The two nodes holding 1 are different objects, so they don't count. Matching values never mean a shared node: compare the nodes themselves.
head_a: 2 -> 7 head_b: 2 -> 7 (separate nodes) returns None
head_a: 1 -> 2 -> 3 head_b is the node 3 of head_a returns that node 3
head_a: None head_b: 8 -> 4 returns None
Return the node object itself, not its value. Don't modify either list. Each list has up to 100,000 nodes. A set of the nodes in one list passes, but try to use O(1) extra memory.
⭐ Bonus: a speed test with lists of up to 100,000 nodes earns a star in O(n + m) time.
Show hint
If the lists had the same length, you could walk them side by side and stop at the first node they share. How can you make up for the difference in length without counting it? Think about what happens if a pointer that reaches the end of one list jumps to the head of the other.