鏈表的歸并排序
超時的代碼
class Solution:def merge(self, head1, head2):if head1 == None:return head2if head2 == None:return head1# head1 and head2 point to the same link listif head1 == head2:return head1head = Nonetail = None# the small pointer point to smaller of two.while head1 and head2:if head1.val <= head2.val:small = head1head1 = head1.nextelse:small = head2head2 = head2.next# the first nodeif tail == None:tail = smallhead = smallelse:tail.next = smalltail = small# link the remaind nodesif head1 == None:head1 = head2tail.next = head1return headdef sortList(self, head):if head == None or head.next == None:return head# we use a fast pointer which go two steps each time and # a slow pointer which go one step each time to get the # middle of the link listslow = headfast = headwhile fast.next and fast.next.next:fast = fast.next.nextslow = slow.next# slow point to the middle nowhead2 = slow.next# we cut of the linked list at middleslow.next = Noneleft = self.sortList(head)right = self.sortList(head2)return self.merge(left, right)主要是在merge的時候。要推斷第一個結點
python中列表sort的用法、AC代碼
class Solution:def merge(self, head1, head2):if head1 == None:return head2if head2 == None:return head1# head1 and head2 point to the same link listif head1 == head2:return head1head = ListNode(-1)tail = head# the small pointer point to smaller of two.while head1 and head2:if head1.val <= head2.val:small = head1head1 = head1.nextelse:small = head2head2 = head2.nexttail.next = smalltail = small# link the remaind nodesif head1 == None:head1 = head2tail.next = head1return head.nextdef sortList(self, head):if head == None or head.next == None:return head# we use a fast pointer which go two steps each time and # a slow pointer which go one step each time to get the # middle of the link listslow = headfast = headwhile fast.next and fast.next.next:fast = fast.next.nextslow = slow.next# slow point to the middle nowhead2 = slow.next# we cut of the linked list at middleslow.next = Noneleft = self.sortList(head)right = self.sortList(head2)return self.merge(left, right)這里merge的時候建立了一個偽頭結點，處理的時候就不用推斷是否為第一個結點，盡管AC，但時間5500ms以上。而c++代碼僅僅須要200多ms，差距還是比較大的
