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

[Animenzzzz]

题目描述：

对链表进行插入排序。

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

插入排序算法：

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

示例 1：

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

示例 2：

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

解题思路：这题我的处理复杂了（看了网上的，网上很简单。。。）。首先对空、只有一个节点、只有两个节点的链表进行处理。分两个指针，首先是head，以及head的后一个p1。p1和head若一直满足p1>head的关系，则一直往后偏移。当遇到p1<head的时候，则说明需要排序了。排序处理：从头遍历之前的链表，可能出现的两种情况：1. p1直接插在头结点 2. p1插在某个中间。
插在头结点：处理做一些变换，注意：更新一下head的值，以及新的头结点

C解题：

struct ListNode* insertionSortList(struct ListNode* head){
    if(!head) return head;
    if(!head->next) return head;
    struct ListNode* result_head = head;
    head = head->next;
    if(head->val < result_head->val){
        result_head->next = head->next;
        head->next = result_head;
        result_head = head;
    }
    
    if(!head->next) return result_head;
    while (head && head->next)
    {
        struct ListNode* p1 = head->next;
        while (p1 && p1->val >= head->val)
        {
            p1 = p1->next;
            head = head->next;
        }
        struct ListNode* result_head_tmp = result_head;
        struct ListNode* result_head_tmp_prefix = NULL;
        while ((p1 && result_head_tmp != p1) && result_head_tmp->val < p1->val)
        {
            result_head_tmp_prefix = result_head_tmp;
            result_head_tmp = result_head_tmp->next;
        }
        //插入头结点
        if (result_head_tmp == result_head)
        {
            if(p1){
                head->next = p1->next;
                p1->next = result_head;
                result_head = p1;
                head = result_head_tmp;
            }
        }else{
            result_head_tmp_prefix->next = p1;
            head->next = p1->next;
            p1->next = result_head_tmp;
        }
    }
    return result_head;
}