:orphan:

Sort List
=========

.. highlight:: none

Problem
-------
https://leetcode.com/problems/sort-list/

Given the ``head`` of a linked list, return *the list after sorting it
in* **ascending order**.

 

**Example 1:**

|image1|

::


   Input: head = [4,2,1,3]
   Output: [1,2,3,4]

**Example 2:**

|image2|

::


   Input: head = [-1,5,3,4,0]
   Output: [-1,0,3,4,5]

**Example 3:**

::


   Input: head = []
   Output: []

 

**Constraints:**

- The number of nodes in the list is in the range
  ``[0, 5 * 10``\ :sup:```4```\ ``]``.
- ``-10``\ :sup:```5```\ ``<= Node.val <= 10``\ :sup:```5```

 

**Follow up:** Can you sort the linked list in ``O(n logn)`` time and
``O(1)`` memory (i.e. constant space)?

.. |image1| image:: https://assets.leetcode.com/uploads/2020/09/14/sort_list_1.jpg
.. |image2| image:: https://assets.leetcode.com/uploads/2020/09/14/sort_list_2.jpg

.. highlight:: python

Pattern
-------
Linked List, Two Pointers, Divide and Conquer, Sorting, Merge Sort

Solution
--------
Use merge sort.

Code
----

.. literalinclude:: ../problems/medium/sort-list/sort_list__approach_1.py
    :language: python
    :lines: 13-

Test
----
>>> from sort_list__approach_1 import ListNode, sortList
>>> head = ListNode.from_list([4, 2, 1, 3])
>>> head = sortList(head)
>>> print(head)
1 -> 2 -> 3 -> 4
>>> head = ListNode.from_list([-1, 5, 3, 4, 0])
>>> head = sortList(head)
>>> print(head)
-1 -> 0 -> 3 -> 4 -> 5

Complexity
----------
| Time: :math:`O(n \log n)` — merge sort
| Auxiliary Space: :math:`O(\log n)`

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

.. autofunction:: sort_list__approach_1.sortList

.. autofunction:: sort_list__approach_1.sort_list

.. autofunction:: sort_list__approach_1.minimum