1. 题目

2. 分析

写链表的题，最需要理清思路。因为思路清晰的情况下，才能保证不出岔子。

3. 代码

# Definition for singly-linked list.
# 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 not head:
            return head
        ss = head # start of sorted 
        
        # 开始插入排序
        head = head.next
        ss.next = None
        while(head):
            tmp = head.next
            # 寻找一个合适的点安排 head 这个指针
            start = ss
            pre = None            
            while(start and start.val <= head.val):
                pre = start
                start = start.next
            if pre:
                pre.next = head # 接上头
                head.next = start # 接上尾部
            else:
                head.next = ss
                ss = head
            head = tmp
        return ss