题目描述：

Sort a linked list in O(n log n) time using constant space complexity.

Python代码：

``````# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
# @param head, a ListNode
# @return a ListNode
def sortList(self, head):
if head is None or head.next is None:
return head
mid = self.getMiddle(head)
rHead = mid.next
mid.next = None
return self.merge(self.sortList(head), self.sortList(rHead))

def merge(self, lHead, rHead):
dummyNode = ListNode(0)
dummyHead = dummyNode
while lHead and rHead:
if lHead.val < rHead.val:
dummyHead.next = lHead
lHead = lHead.next
else:
dummyHead.next = rHead
rHead = rHead.next
dummyHead = dummyHead.next
if lHead:
dummyHead.next = lHead
elif rHead:
dummyHead.next = rHead
return dummyNode.next

def getMiddle(self, head):
if head is None:
return head
slow = head
fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
return slow
``````

Pingbacks已关闭。

1. Mr.Shuo 发布于 2016年6月17日 10:46 #

这里有一点错误的东西，对于merge之后剩下的元素不能保证其正确顺序。可以使用递归的归并方法来避免。