Merge Two Sorted Linked Lists

EasyLinked listTwo pointersSorting183 tests

You are given a and b, the first nodes of two singly linked lists. Each list is sorted in non-decreasing order (each value is equal to or larger than the value before it).

Join the two lists into one list that is also sorted in non-decreasing order, and return its first node.

Build the result from the nodes you already have: change their next links. You do not need to create new nodes.

Note

Either list can be empty (its first node is null, or None in Python). If both are empty, return null.
When values are equal, their order in the result does not matter, because the judge compares values only.

How the input is shown

A list is written as an array of its values from first node to last node. For example, [1, 4, 4] is the list 1 -> 4 -> 4. Your function gets the first node of each list, not the arrays.

Hint: a dummy start node makes the code shorter. Keep a pointer to the last node of the result. At each step, attach the smaller of the two front nodes and move forward in that list. When one list ends, attach the rest of the other list.

Examples

Example 1

Input:: [2,5,9], [3,5,6,12]
Output:: [2,3,5,5,6,9,12]

Take the smaller front value each time: 2 (from a), 3 (from b), 5, 5, 6 (from b), 9 (from a). Then a is used up, so 12 is attached at the end.

Example 2

Input:: [], [-4,0]
Output:: [-4,0]

The first list is empty, so the answer is the second list.

Example 3

Input:: [10,11], [1,2,3]
Output:: [1,2,3,10,11]

Every value in b is smaller than every value in a, so all of b comes first.

Constraints

Each list has 0 to 25 nodes.
-50 <= val <= 50
Both lists are sorted in non-decreasing order.

Run checks your code against the 3 examples. Submit checks it against all 183 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.