[LeetCode 147] Insertion Sort List

[LeetCode 147][] Sort a linked list using insertion sort.

Diffculty
Medium

Similar Problems
[LeetCode 148] Sort List Medium

Analysis

单向链表，只能从前往后依次遍历比较和交换。

由于排序后头节点不一定，故需要引入 dummy node，并以此节点的 next 作为最后返回结果的头节点。返回的链表从 dummy->next 这里开始构建。 我们需要记录一个已经排序的序列，其是从 dummy node 开始的一段列表，是在链表前面部分， 每次循环都从 dummy->next 开始遍历，依次和上一轮处理到的节点的值进行比较，直至找到不小于上一轮节点值的节点为止，随后将上一轮节点插入到当前遍历的节点之前，依此类推。文字描述起来可能比较模糊，大家可以结合以下的代码在纸上分析下。

每次插入，就是把 cur 插到 pre 后面，具体过程就是：

ListNode *temp = cur->next;
cur->next = pre->next;
pre->next = cur;
cur = temp;

优化 先判断链表是否有序，仅对降序的部分进行处理。

Solutions

class Solution {
public:
    ListNode* insertionSortList(ListNode *head) {  
        if(head == nullptr || head->next == nullptr) return head;
        ListNode *dummy = new ListNode(0);
        ListNode *cur = head;
        while(cur != nullptr) { // 依次遍历每个节点
            ListNode *pre = dummy;
            while(pre->next != nullptr && pre->next->val < cur->val) // 遍历已排序的那部分链表
                pre = pre->next;

            ListNode *temp = cur->next;
            cur->next = pre->next;
            pre->next = cur;
            cur = temp;
        }
        return dummy->next;
    }
};

优化后的代码

class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *cur = head;
        while (cur != NULL) {
            if (cur->next != NULL && cur->next->val < cur->val) {
                ListNode *pre = dummy;
                // find insert position for smaller(cur->next)
                while (pre->next != NULL && pre->next->val <= cur->next->val) {
                    pre = pre->next;
                }
                // insert cur->next after pre
                ListNode *temp = pre->next;
                pre->next = cur->next;
                cur->next = cur->next->next;
                pre->next->next = temp;
            } else {
                cur = cur->next;
            }
        }
        return dummy->next;
    }
};

分析：

• 新建 dummy 节点并将其next 指向head
• 分情况讨论，仅需要处理逆序部分。
• 由于已经确认链表逆序，故仅需将较小值(cur->next 而不是 cur )的节点插入到链表的合适位置。
• 将 cur->next 插入到pre之后，这里需要四个步骤，需要特别小心！

如上图所示，将cur->next插入到pre节点后大致分为3个步骤。

[LeetCode 147]: