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