1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution
{
public:
    ListNode* insertionSortList(ListNode* head)
    {
        // 创建虚拟头节点
        ListNode* dummy = new ListNode(-1);
        ListNode* p = head;

        // 遍历原链表
        while (p)
        {
            // 找到插入点：从 dummy 开始找到第一个大于当前节点值的位置
            ListNode* cur = dummy;
            while (cur->next && cur->next->val <= p->val)
                cur = cur->next;

            // 插入当前节点到有序链表
            ListNode* next = p->next;  // 保存下一个节点
            p->next = cur->next;      // 当前节点指向插入位置后的节点
            cur->next = p;            // 插入当前节点到有序链表
            p = next;                 // 继续处理下一个节点
        }

        // 返回排序后的链表
        return dummy->next;
    }
};