Sort List
LeetCode 148
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
Time Complexity: O(n)
"""
if not head or not head.next:
return head
slow = fast = head
# 切對半 為何先 fast 在 fast.next 不能對調, 因為fast.next
while fast and fast.next:
fast = fast.next.next
pre = slow
slow = slow.next
pre.next = None
head2 = slow
left = self.sortList(head)
right = self.sortList(head2)
return self.merge(left, right)
def merge(self, left, right):
# 對於 sinlge linked list 的 add 或 delete node 最好有 dummy node 會省事很多
dummy = node = ListNode(0)
while left and right:
if left.val < right.val:
node.next = left
left = left.next
else:
node.next = right
right = right.next
node = node.next
# if not left return right else return left
node.next = left or right
return dummy.next
Last updated