原题地址
    题解：

    1. # Definition for singly-linked list.
    2. # class ListNode:
    3. #     def __init__(self, x):
    4. #         self.val = x
    5. #         self.next = None
    7. class Solution:
    8.     def insertionSortList(self, head: ListNode) -> ListNode:
    9.         if head is None:
    10.             return head
    12.         head_node = ListNode(0)        # 创建一个临时节点（空列表）
    13.         head_node.next = head        # 将原来列表的头节点挂到新的链表上
    15.         cur_node = head.next        # cur_node代表当前需要进行排序的节点
    16.         last_sorted_node = head        # last_sorted_node代表已经经过了排序的所有结点的尾部节点
    18.           # 使用第二个节点开始排序，第一个节点作为基点
    20.         while cur_node:        # 一直循环到链表尾部
    21.             if last_sorted_node.val <= cur_node.val:    # 判断当前排序节点值和已排序部分尾部节点值的关系
    22.                 last_sorted_node = cur_node        # 如果cur >= last_sorted_node, 不需要插入
    23.             else:            # 如果cur < last_sorted_node, 需要将cur_node插入到已排序部分中
    24.                 prev_node = head_node        # 针对已排序部分，从头部开始遍历，寻找合适的位置
    25.                 while prev_node.next.val <= cur_node.val:
    26.                     prev_node = prev_node.next
    27.                 last_sorted_node.next = cur_node.next    # 将cur_node插入到指定位置上
    28.                 cur_node.next = prev_node.next
    29.                 prev_node.next = cur_node
    31.             cur_node = last_sorted_node.next
    33.         return head_node.next