LeetCode 148. Sort List

Description

https://leetcode.com/problems/shuffle-the-array/

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

Constraints:

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

Explanation

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
            else:
                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.