- merge sort
"""
Definition of ListNode
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
@param: head: The head of linked list.
@return: You should return the head of the sorted linked list, using constant space complexity.
"""
def sortList(self, head):
# write your code here
if not head:
return None
return self.merge_sort(head)
def merge_sort(self, head):
if head.next == None:
return head
left_start = head
right_start = self.split_list(head)
left = self.merge_sort(left_start)
right = self.merge_sort(right_start)
return self.merge(left, right)
def merge(self, left, right):
dummy_head = ListNode(0)
head = dummy_head
while left != None and right != None:
if left.val <= right.val:
head.next = left
left = left.next
else:
head.next = right
right = right.next
head = head.next
if left != None:
head.next = left
if right != None:
head.next = right
return dummy_head.next
def split_list(self, head):
slow = head
fast = head
while fast.next != None and fast.next.next != None:
slow = slow.next
fast = fast.next.next
tmp = slow.next
slow.next = None
return tmp
quick sort
"""
Definition of ListNode
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
@param: head: The head of linked list.
@return: You should return the head of the sorted linked list, using constant space complexity.
"""
def sortList(self, head):
# write your code here
if not head:
return head
return self.quick_sort(head)
def quick_sort(self, head):
#exit
if head == None or head.next == None:
return head
dummy_left = ListNode(0)
left_head = dummy_left
dummy_middle = ListNode(0)
middle_head = dummy_middle
dummy_right = ListNode(0)
right_head = dummy_right
pivot_node = self.find_middle(head)
while head != None:
if head.val > pivot_node.val:
right_head.next = head
right_head = right_head.next
elif head.val < pivot_node.val:
left_head.next = head
left_head = left_head.next
else:
middle_head.next = head
middle_head = middle_head.next
head = head.next
#cut the tie on each one
right_head.next = None
middle_head.next = None
left_head.next = None
return self.merge(self.quick_sort(dummy_left.next),
dummy_middle.next,
self.quick_sort(dummy_right.next))
def merge(self, left_head, middle_head, right_head):
if left_head == None:
dummy_node = middle_head
else:
dummy_node = left_head
while left_head != None and left_head.next != None:
left_head = left_head.next
if left_head != None:
left_head.next = middle_head
while middle_head.next != None:
middle_head = middle_head.next
middle_head.next = right_head
return dummy_node
def find_middle(self, head):
slow = head
fast = head
while fast.next != None and fast.next.next != None:
slow = slow.next
fast = fast.next.next
return slow