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.