:orphan:

Merge Two Sorted Lists
======================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/merge-two-sorted-lists/

You are given the heads of two sorted linked lists ``list1`` and
``list2``.

Merge the two lists into one **sorted** list. The list should be made by
splicing together the nodes of the first two lists.

Return *the head of the merged linked list*.

 

**Example 1:**

|image1|

::


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

**Example 2:**

::


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

**Example 3:**

::


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

 

**Constraints:**

- The number of nodes in both lists is in the range ``[0, 50]``.
- ``-100 <= Node.val <= 100``
- Both ``list1`` and ``list2`` are sorted in **non-decreasing** order.

.. |image1| image:: https://assets.leetcode.com/uploads/2020/10/03/merge_ex1.jpg

.. highlight:: python

Pattern
-------
Linked List, Recursion

Solution
--------
Create the new list by selecting the minimum node of ``list1`` and ``list2``,
checking if either is ``None``. Set the ``next`` field of the previous node to
the minimum node. Advance the ``list1``/``list2`` and previous node pointers.

Code
----

.. literalinclude:: ../problems/easy/merge-two-sorted-lists/merge_two_sorted_lists__approach_1.py
    :language: python
    :lines: 10-

Test
----
>>> from merge_two_sorted_lists__approach_1 import ListNode, merge_2_lists
>>> head1 = ListNode.from_list([1, 2, 4])
>>> head2 = ListNode.from_list([1, 3, 4])
>>> head = merge_2_lists(head1, head2)
>>> print(head)
1 -> 1 -> 2 -> 3 -> 4 -> 4

Complexity
----------
| :math:`m` is the length of the first input list and :math:`n` is the length of the second input list
| Time: :math:`O(m + n)` — go through both lists
| Auxiliary Space: :math:`O(1)`

.. autoclass:: merge_two_sorted_lists__approach_1.ListNode
   :members:
   :show-inheritance:
   :undoc-members:

.. autofunction:: merge_two_sorted_lists__approach_1.merge_2_lists

.. autofunction:: merge_two_sorted_lists__approach_1.minimum