Merge Two Sorted Lists

You are given the heads of two linked lists, list1 and list2, each sorted from smallest to largest. Merge them into one sorted list by linking their nodes together, and return its head.

Lists in the examples are written as their values from head to tail: [1,2,3] is 1 → 2 → 3, and [] is an empty list, with no head at all.

Constraints

  • 0 ≤ number of nodes in each list ≤ 5,000
  • -10,000 ≤ node value ≤ 10,000
  • Both lists are sorted in non-decreasing order.

Example 1

Input
list1 = [1,2,4]
list2 = [1,3,4]
Output
[1,1,2,3,4,4]
Why:

Take the smaller head each time: 1, 1, 2, 3, 4, 4.

Example 2

Input
list1 = []
list2 = []
Output
[]
Why:

Two empty lists merge into an empty list.

Example 3

Input
list1 = []
list2 = [0]
Output
[0]
Why:

With one list empty, the answer is the other list.

Hints

    Was this a good challenge?

    Solved by
    0
    Submissions
    0
    Accepted
    –