noodleProblems/
Merge Two Sorted Lists
#31

Merge Two Sorted Lists

AlgorithmeasyLinked ListRecursion

You are given the heads of two sorted linked lists, list1 and list2. Each list is sorted in **non-decreasing** order.

Splice the two lists together into a single sorted linked list and return its head. The merged list should be assembled from the nodes of the two input lists, preserving non-decreasing order.

Either list may be empty. Lists are shown in array notation for readability — [1, 2, 4] is the chain 1 -> 2 -> 4, and [] is an empty list.

Example cases

  • interleaved
    in list1 = [1,2,4]124nulllist2 = [1,3,4]134null
    out [1,1,2,3,4,4]112344null
    Merging 1->2->4 with 1->3->4 yields 1->1->2->3->4->4.
  • both empty
    in list1 = []nulllist2 = []null
    out []null
  • one empty
    in list1 = []nulllist2 = [0]0null
    out [0]0null
    An empty list merged with 0 is just 0.

Constraints

  • The number of nodes in each list is in the range [0, 50].
  • -100 <= Node.val <= 100
  • Both list1 and list2 are sorted in non-decreasing order.
Saved
list1 =
[1,2,4]
list2 =
[1,3,4]