0148-sort-list

Try it on leetcode

Description

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

 

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

 

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

Solution(Python)

# 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 | None) -> ListNode | None:
        return self.bottomup(head)

    def mergesort(self, head: ListNode | None) -> ListNode | None:
        # split
        # process left and right
        # merge
        if not head or not head.next:
            return head
        slow = head
        fast = head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        mid = slow.next
        slow.next = None

        left = self.sortList(head)
        right = self.sortList(mid)

        mergedHead = ListNode()
        cur = mergedHead
        while left and right:
            if left.val <= right.val:
                cur.next = left
                left = left.next
            else:
                cur.next = right
                right = right.next
            cur = cur.next
        
        cur.next = left or right
        return mergedHead.next

    def bottomup(self, head: ListNode | None) -> ListNode | None:
        # get n
        # start size = 1
        # size < n size*2 < n
        #  left cur
        #  split left,size
        # cur split right,size
        # merge eft and right
        #
        
        if not head or not head.next:
            return head

        n = 0

        cur = head
        while cur: # 1 -> 2 -> 3  : n= 3  cur = None
            n += 1 
            cur = cur.next

        size = 1
        sortHead = ListNode(0, head)
        while size < n:
            tail =  sortHead
            cur = tail.next
            while cur:
                left = cur
                right = self.split(left, size)
                cur = self.split(right, size)
                tail = self.merge(left, right, tail)
            size *= 2

        return sortHead.next

    def split(self, node, size):
        cur = node
        for _ in range(size - 1):
            if not node:
                return None
            node = node.next
        if not node:
            return None
        tail = node.next
        node.next = None
        return tail

    def merge(self, left, right, tail):
        cur = tail
        while left and right:
            if left.val <= right.val:
                cur.next= left
                left = left.next
            else:
                cur.next = right
                right = right.next
            cur = cur.next
        cur.next = left or right
        while cur.next:
            cur = cur.next
        return cur