#156EasyLinked Lists· Splicing Sorted Lists

Merge Delivery Routes

Two warehouses each keep the stops of a delivery route as a singly linked list, ordered by distance from the depot, nearest first. A third van is taking over both routes, so the dispatcher needs a single route that visits every stop of both lists, still in order of distance. Merge the two sorted linked lists `a` and `b` into one sorted linked list and return its head. Build the result by **re-linking the existing nodes**, not by creating a copy of every value. When two stops are equally far away, either order is acceptable, because the output only exposes their distances.

Input format

`a` and `b`: heads of two singly linked lists, each given as an array of integers in non-decreasing order.

Output format

The merged list as an array in non-decreasing order.

Examples

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

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

Taking the smaller head each time yields 1, 2, 3, 4, 5, 6.

Input: a = [], b = [7, 8]

Output: [7, 8]

An empty route contributes nothing, so the result is the other list unchanged.

Input: a = [1, 1, 4], b = [1, 3]

Output: [1, 1, 1, 3, 4]

Equal distances may come from either list; the merged distances are 1, 1, 1, 3, 4.

Constraints

0 <= length of each list <= 5 * 10^4
-10^6 <= node value <= 10^6
Both lists are sorted in non-decreasing order; either may be empty.

#linked-list
#two-pointers
#merge