All problems

Merge Alternating Lists

Easy · linked list

You are given the heads of two singly linked lists, a and b. Build one list by taking a node from a, then a node from b, then the next node from a, then the next from b, and so on, always starting with a. Each list is read from its front, in its own order.

When one list runs out, the rest of the other list goes at the end, in order. Return the head of the combined list. If both lists are empty, return None.

The nodes you receive are ListNode objects with a val and a next. The result must contain every value from both lists exactly once.

Examples

Example 1

Input: a = [1, 2, 3], b = [10, 20, 30]

Output: [1, 10, 2, 20, 3, 30]

The lists are the same length, so they alternate all the way: 1, 10, 2, 20, 3, 30.

Example 2

Input: a = [1, 2, 3, 4, 5], b = [9]

Output: [1, 9, 2, 3, 4, 5]

After 1 and 9, list b is empty, so 2, 3, 4, 5 follow in order.

Example 3

Input: a = [], b = [4, 5]

Output: [4, 5]

List a has nothing to give, so the result is just b.

Constraints