leetcode 【 Sort List 】 python 实现
题目：Sort a linked list in O(n log n) time using constant space complexity.
代码：oj 测试通过 Runtime: 372 ms
1 # Definition for singly-linked list.
2 # class ListNode:
3 # def __init__(self, x):
4 # self.val = x
5 # self.next = None
6
7 class Solution:
8 # @param head, a ListNode
9 # @return a ListNode
10 def sortList(self, head):
11
12 if head is None or head.next is None:
13 return head
14
15 slow = head
16 fast = head
17
18 while fast.next is not None and fast.next.next is not None:
19 slow = slow.next
20 fast = fast.next.next
21
22 h1 = head
23 h2 = slow.next
24 slow.next = None
25 l1 = self.sortList(h1)
26 l2 = self.sortList(h2)
27 head = self.mergeTwoLists(l1,l2)
28
29 return head
30
31 # merger two sorted list
32 def mergeTwoLists(self, l1, l2):
33 if l1 is None:
34 return l2
35 if l2 is None:
36 return l1
37
38 p = ListNode(0)
39 dummyhead = p
40
41 while l1 is not None and l2 is not None:
42 if l1.val > l2.val:
43 p.next = l2
44 l2 = l2.next
45 else:
46 p.next = l1
47 l1 = l1.next
48 p = p.next
49
50 if l1 is None:
51 p.next = l2
52 else:
53 p.next = l1
54
55 return dummyhead.next
思路：
归并排序的原理无需多说，感觉像小学老师给卷子排序：每个小组的组内成绩由低到高排序；小组长再交给大组长；大组长再交给老师。
小白实现的步骤是先测试通过mergeTwoLists函数，实现两个有序list的合并。详情见http://www.cnblogs.com/xbf9xbf/p/4186905.html这篇日志。
在实现两个有序链表的合并基础上，再在主程序写递归程序。
页:
[1]