链表的归并排序
超时的代码
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，差距还是比較大的