LeetCode 148. Sort List



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

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

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: []


  • The number of nodes in the list is in the range [0, 5 * 104].
  • -105 <= Node.val <= 105


Use merge sort and use a find middle helper function.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: ListNode) -> ListNode:

        return self.merge_sort(head)
    def find_middle(self, head):
        if not head or not head.next:
            return head
        fast = head.next
        slow = head
        while fast.next and fast.next.next:
            slow = slow.next            
            fast = fast.next.next            
        return slow
    def merge(self, l1, l2):       
        dummy = ListNode(0)
        l3 = dummy

        while l1 and l2:
            if l1.val <= l2.val:
                l3.next = l1
                l1 = l1.next
                l3.next = l2
                l2 = l2.next
            l3 = l3.next
        if l1:
            l3.next = l1
        if l2:
            l3.next = l2
        return dummy.next
    def merge_sort(self, head):
        if not head or not head.next:
            return head
        middle = self.find_middle(head)

        right = self.merge_sort(middle.next)
        middle.next = None
        left = self.merge_sort(head)        
        return self.merge(left, right)
  • Time complexity: O(N logN).
  • Space complexity: O(log N). where N is the number of nodes in the linked list. Since the problem is recursive, we need additional space to store the recursive call stack. The maximum depth of the recursion tree is log N.

Leave a Reply

Your email address will not be published. Required fields are marked *