链表的归并排序
超时的代码
class Solution: def merge(self, head1, head2): if head1 == None: return head2 if head2 == None: return head1 # head1 and head2 point to the same link list if head1 == head2: return head1 head = None tail = None # the small pointer point to smaller of two. while head1 and head2: if head1.val <= head2.val: small = head1 head1 = head1.next else: small = head2 head2 = head2.next # the first node if tail == None: tail = small head = small else: tail.next = small tail = small # link the remaind nodes if head1 == None: head1 = head2 tail.next = head1 return head def 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 list slow = head fast = head while fast.next and fast.next.next: fast = fast.next.next slow = slow.next # slow point to the middle now head2 = slow.next # we cut of the linked list at middle slow.next = None left = self.sortList(head) right = self.sortList(head2) return self.merge(left, right)
主要是在merge的时候，要判断第一个结点
AC代码
class Solution: def merge(self, head1, head2): if head1 == None: return head2 if head2 == None: return head1 # head1 and head2 point to the same link list if head1 == head2: return head1 head = ListNode(-1) tail = head # the small pointer point to smaller of two. while head1 and head2: if head1.val <= head2.val: small = head1 head1 = head1.next else: small = head2 head2 = head2.next tail.next = small tail = small # link the remaind nodes if head1 == None: head1 = head2 tail.next = head1 return head.next def 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 list slow = head fast = head while fast.next and fast.next.next: fast = fast.next.next slow = slow.next # slow point to the middle now head2 = slow.next # we cut of the linked list at middle slow.next = None left = self.sortList(head) right = self.sortList(head2) return self.merge(left, right)
这里merge的时候建立了一个伪头结点，处理的时候就不用判断是否为第一个结点，虽然AC，但时间5500ms以上，而c++代码只需要200多ms，差距还是比较大的