链表的归并排序

超时的代码

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)

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)