Friedrich Ewald My Personal Website

Leetcode: Sort list

Given a single linked list, sort the values in ascending order.

# Example
Input: (4)->(3)->(1)->(2)
Output: (1)->(2)->(3)-(4)
The solution for the single linked list looks as follows. It has a time complexity of O(n*log(n)). The technique here is first split the list in two lists of (almost) equal length. Then split the resulting lists again along the middle until the list contains only 1 or 0 elements. This leaves only at most 2 elements to compare. If the left one is less than the right one, attach the left one to and vice versa. This small list is now sorted. When going up the stack, the left and right lists are therefore sorted as well and can be merged in a similar fashion. This ultimately results in a completely sorted list.
from typing import Optional

# Definition for singly-linked list.
class ListNode:
  def __init__(self, val=0, next=None):
    self.val = val = next
  def __str__(self) -> str:
    s = f"{self.val}"
    if is not None:
      s += f", {}"
    return s

class Solution:
  def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    return self.mergeSort(head)

  def mergeSort(self, h):
    if h is None or is None:
      return h

    middle = self.findMiddle(h)
    middle_next = = None

    left = self.mergeSort(h)
    right = self.mergeSort(middle_next)
    sorted_list = self.sort(left, right)
    return sorted_list
  def sort(self, l, r):
    result = None

    if l is None:
      return r
    if r is None:
      return l
    if l.val <= r.val:
      result = l = self.sort(, r)
      result = r = self.sort(l,
    return result

  def findMiddle(self, head):
    if head is None:
      return head
    slow = head
    fast = head
    while is not None and is not None:
      slow =
      fast =
    return slow

if __name__ == '__main__':
  s = Solution().sortList
  print(s(ListNode(4, ListNode(2, ListNode(1, ListNode(3))))), [1,2,3,4])
Runtime: 1282 ms, faster than 22.47% of Python3 online submissions for Sort List. Memory Usage: 86.7 MB, less than 5.62% of Python3 online submissions for Sort List.
Another option is a merge sort for a standard list in Python:
class Solution:
  def sortList(self, l):
    return self.mergeSort(l)

  def mergeSort(self, l):
    # If the length of the list is one element or less,
    # return it as it means we reached the innermost
    # recursion.
    if len(l) <= 1:
      return l

    # Find middle element with floor integer division
    middle = len(l) // 2

    # Recursively create left and right until left and right are only
    # one element long, then merge
    left = self.mergeSort(l[:middle])
    right = self.mergeSort(l[middle:])

    pl = 0
    pr = 0
    sorted_list = []
    while pl < len(left) and pr < len(right):
      if left[pl] <= right[pr]:
        pl += 1
        pr += 1
    # Add the remainders of the list
    sorted_list += left[pl:]
    sorted_list += right[pr:]
    return sorted_list

if __name__ == '__main__':
  s = Solution().sortList
  print(s([4,3,1,2]), [1,2,3,4])

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.