Sort List

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:

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

Example 2:

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)?

Pattern

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

Approaches

Merge Sort

Explanation

Use merge sort.

Code

from __future__ import annotations


class ListNode:
    """Node in a linked list."""

    def __init__(self, val: int, next: ListNode | None = None):
        self.val = val
        self.next = next

    def __str__(self) -> str:
        suffix = " -> " + str(self.next) if self.next else ""
        return str(self.val) + suffix

    @classmethod
    def from_list(cls, list: list[int]) -> ListNode | None:
        head = None
        for el in list:
            if head is None:
                head = ListNode(el)
                node = head
            else:
                node.next = ListNode(el)
                node = node.next
        return head


def sortList(head: ListNode | None) -> ListNode | None:
    """Sort linked list."""
    node = head
    length = 0
    while node is not None:
        node = node.next
        length += 1

    return sort_list(head, length)


def sort_list(head: ListNode | None, length: int):
    """Sort a linked list of length ``length`` with merge sort."""
    if length <= 1:
        return head

    node = head
    midpoint = length // 2
    for i in range(midpoint - 1):
        node = node.next
    next_node = node.next
    node.next = None

    left_head = sort_list(head, midpoint)
    right_head = sort_list(next_node, length - midpoint)

    new_head = None
    prev_node = None

    while left_head is not None or right_head is not None:
        node, left_head, right_head = minimum(left_head, right_head)
        if new_head is None:
            new_head = node
        elif prev_node is not None:
            prev_node.next = node
        prev_node = node
        node = node.next

    return new_head


def minimum(
    list1: ListNode | None, list2: ListNode | None
) -> tuple[ListNode | None]:
    """Return the minimum node of ``list1`` and ``list2`` and advances the that
    pointer.
    """
    if list1 is None and list2 is None:
        return None, None, None
    elif list1 is None:
        return list2, None, None
    elif list2 is None:
        return list1, None, None
    elif list1.val < list2.val:
        return list1, list1.next, list2
    else:
        return list2, list1, list2.next

Test

>>> from sort_list__merge_sort 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

Measure	Complexity	Notes
Time	\(O(n \log n)\)	merge sort
Auxiliary Space	\(O(\log n)\)

class sort_list__merge_sort.ListNode(val: int, next: ListNode | None = None)

Bases: object

Node in a linked list.

classmethod from_list(list: list[int]) → ListNode | None

sort_list__merge_sort.sortList(head: ListNode | None) → ListNode | None

Sort linked list.

sort_list__merge_sort.sort_list(head: ListNode | None, length: int)

Sort a linked list of length length with merge sort.

sort_list__merge_sort.minimum(list1: ListNode | None, list2: ListNode | None) → tuple[ListNode | None]

Return the minimum node of list1 and list2 and advances the that pointer.