首页 > 代码库 > leetcode 【 Sort List 】 python 实现
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 ListNode10 def sortList(self, head):11 12 if head is None or head.next is None:13 return head14 15 slow = head16 fast = head17 18 while fast.next is not None and fast.next.next is not None:19 slow = slow.next20 fast = fast.next.next21 22 h1 = head23 h2 = slow.next24 slow.next = None25 l1 = self.sortList(h1)26 l2 = self.sortList(h2)27 head = self.mergeTwoLists(l1,l2)28 29 return head30 31 # merger two sorted list32 def mergeTwoLists(self, l1, l2):33 if l1 is None:34 return l235 if l2 is None:36 return l137 38 p = ListNode(0)39 dummyhead = p40 41 while l1 is not None and l2 is not None:42 if l1.val > l2.val:43 p.next = l244 l2 = l2.next45 else:46 p.next = l147 l1 = l1.next48 p = p.next49 50 if l1 is None:51 p.next = l252 else:53 p.next = l154 55 return dummyhead.next
思路：
归并排序的原理无需多说，感觉像小学老师给卷子排序：每个小组的组内成绩由低到高排序；小组长再交给大组长；大组长再交给老师。
小白实现的步骤是先测试通过mergeTwoLists函数，实现两个有序list的合并。详情见http://www.cnblogs.com/xbf9xbf/p/4186905.html这篇日志。
在实现两个有序链表的合并基础上，再在主程序写递归程序。
leetcode 【 Sort List 】 python 实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。