题目：

题解：

class Solution:def sortList(self, head: ListNode) -> ListNode:def merge(head1: ListNode, head2: ListNode) -> ListNode:dummyHead = ListNode(0)temp, temp1, temp2 = dummyHead, head1, head2while temp1 and temp2:if temp1.val <= temp2.val:temp.next = temp1temp1 = temp1.nextelse:temp.next = temp2temp2 = temp2.nexttemp = temp.nextif temp1:temp.next = temp1elif temp2:temp.next = temp2return dummyHead.nextif not head:return headlength = 0node = headwhile node:length += 1node = node.nextdummyHead = ListNode(0, head)subLength = 1while subLength < length:prev, curr = dummyHead, dummyHead.nextwhile curr:head1 = currfor i in range(1, subLength):if curr.next:curr = curr.nextelse:breakhead2 = curr.nextcurr.next = Nonecurr = head2for i in range(1, subLength):if curr and curr.next:curr = curr.nextelse:breaksucc = Noneif curr:succ = curr.nextcurr.next = Nonemerged = merge(head1, head2)prev.next = mergedwhile prev.next:prev = prev.nextcurr = succsubLength <<= 1return dummyHead.next