leetcode 【 Sort List 】 python 实现

disl

　　题目：
　　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这篇日志。
　　在实现两个有序链表的合并基础上，再在主程序写递归程序。