题目:
题解:
class Solution:def insertionSortList(self, head: ListNode) -> ListNode:if not head:return headdummyHead = ListNode(0)dummyHead.next = headlastSorted = headcurr = head.nextwhile curr:if lastSorted.val <= curr.val:lastSorted = lastSorted.nextelse:prev = dummyHeadwhile prev.next.val <= curr.val:prev = prev.nextlastSorted.next = curr.nextcurr.next = prev.nextprev.next = currcurr = lastSorted.nextreturn dummyHead.next