147_对链表进行插入排序.md

147.对链表进行插入排序

问题

对链表进行插入排序。

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。 每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

插入排序算法：

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

示例 1：
输入: 4->2->1->3
输出: 1->2->3->4

示例 2：
输入: -1->5->3->4->0
输出: -1->0->3->4->5

解答

插入排序的链表实现，加一个辅助的节点来作为result的head比较好，方便后面的一些操作，处理一些特殊情况。

主要的问题在于insert()函数的实现，其实也就是一个判断，next是否为nullptr或者大于了node->val，如果是，就找到了插入的地方，插入就好了。

/**
 * 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* node = head, *next;
        ListNode* result = new ListNode(INT_MIN);
        while (node) {
            next = node->next;
            insert(result, node);
            node = next;
        }
        return result->next;
    }
    
    void insert(ListNode* list, ListNode* node) {
        ListNode* now = list;
        while (now) {
            if (!now->next || node->val <= now->next->val) {
                ListNode* next = now->next;
                now->next = node;
                node->next = next;
                return;
            } else {
                now = now->next;
            }
        }
    }
};