题目描述

使用插入排序对一个链表排序。

上图给了一个插入排序的图示。初始时排好序的链表只包含原链表的第一个节点，每次迭代将原链表中的节点使用原地算法插入排好序的链表。

插入排序算法步骤：

1. 从前往后扫描原链表，每次将一个原链表的节点插入结果链表；
2. 要插入到结果链表的合适位置，使得插入后的链表有序；
3. 扫描完原链表后，算法结束；

样例1

输入：4->2->1->3
输出：1->2->3->4

样例2

输入：-1->5->3->4->0
输出：-1->0->3->4->5

算法

(插入排序) $O(n^2)$

为了方便处理边界情况，我们建立虚拟头结点，指向原链表头部。
然后扫描原链表，对于每个节点 $v$，从前往后扫描结果链表，找到第一个比 $v$ 大的节点 $u$，将 $v$ 插入到 $u$ 之前。

时间复杂度分析：一共遍历 $n$ 个节点，对于每个节点找合适位置时，最多需要遍历 $O(n)$ 次，所以总时间复杂度是 $O(n^2)$。

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode *dummy = new ListNode(-1);
        while (head)
        {
            ListNode *next = head->next;
            ListNode *p = dummy;
            while (p->next && p->next-> val <= head->val) p = p->next;

            head->next = p->next;
            p->next = head;

            head = next;
        }
        return dummy->next;
    }
};