Given the heads of two singly linked lists a and b, merge them alternately: the first node of a, then the first of b, then the second of a, then the second of b, and so on. When one list runs out, append the rest of the other list. Return the head of the merged list.
Examples
Input: a = 1 -> 2 -> 3, b = 10 -> 20
Output: 1 -> 10 -> 2 -> 20 -> 3
Input: a = 1, b = 10 -> 20 -> 30
Output: 1 -> 10 -> 20 -> 30
Constraints
0 <= len(a), len(b) <= 10**4- Target: O(len(a) + len(b)) time, O(1) extra space; reuse the existing nodes
Goals
- Build a result by relinking existing nodes, not copying values
- Attach whatever remains of the longer list at the end