Solution
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None:
return head
dummy = ListNode(head.val, head)
pre, cur = dummy, head
while cur:
if pre.val <= cur.val:
pre, cur = cur, cur.next
continue
p = dummy
while p.next.val <= cur.val:
p = p.next
t = cur.next
cur.next = p.next
p.next = cur
pre.next = t
cur = t
return dummy.next
def print_link(head):
res = []
p = head
while p:
res.append(str(p.val))
p = p.next
print(" ".join(res))
if __name__ == "__main__":
# 4->2->1->3
n1 = ListNode(4)
n2 = ListNode(2)
n3 = ListNode(1)
n4 = ListNode(3)
n1.next = n2
n2.next = n3
n3.next = n4
sol = Solution()
new_head = sol.insertionSortList(n1)
print_link(new_head)