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 right.next 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
    self.next = next
  
  def __str__(self) -> str:
    s = f"{self.val}"
    if self.next is not None:
      s += f", {self.next}"
    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 h.next is None:
      return h

    middle = self.findMiddle(h)
    middle_next = middle.next
    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
      result.next = self.sort(l.next, r)
    else:
      result = r
      result.next = self.sort(l, r.next)
    return result

  def findMiddle(self, head):
    if head is None:
      return head
    slow = head
    fast = head
    while fast.next is not None and fast.next.next is not None:
      slow = slow.next
      fast = fast.next.next
    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]:
        sorted_list.append(left[pl])
        pl += 1
      else:
        sorted_list.append(right[pr])
        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 a Staff 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.

Related Posts