[LeetCode] 147. 对链表进行插入排序

给定单个链表的头 head ，使用插入排序对链表进行排序，并返回排序后链表的头 。

插入排序 算法的步骤:

1. 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
2. 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
3. 重复直到所有输入数据插入完为止。

下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。

对链表进行插入排序。

示例 1：

输入: head = [4,2,1,3] 输出: [1,2,3,4]

示例 2：

输入: head = [-1,5,3,4,0] 输出: [-1,0,3,4,5]

思路:

用lastSorted->val <= curr->val先判断当前节点是否已经有序， 如果无序则从dummy开始往后查找插入位置， 找到位置直接做一次标准的链表插入链表的操作就行。即:

lastSorted->next = curr->next;
curr->next = prev->next;
prev->next = curr;Code language: C++ (cpp)

AC代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        
        ListNode* lastSorted = head;
        ListNode* curr = head->next;
        
        while (curr) {
            if (lastSorted->val <= curr->val) {
                lastSorted = lastSorted->next;
            } else {
                ListNode* prev = dummy;
                while (prev->next->val <= curr->val) {
                    prev = prev->next;
                }
                lastSorted->next = curr->next;
                curr->next = prev->next;
                prev->next = curr;
            }
            curr = lastSorted->next;
        }
        
        ListNode* result = dummy->next;
        delete dummy;
        return result;
    }
};Code language: C++ (cpp)