insertion-sort-list

题目描述
使用插入排序对链表进行排序。
Sort a linked list using insertion sort.

/**
 * 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) {
        if(head==NULL||head->next==NULL) return head;
        ListNode  temp(0); // 虚拟头节点
        ListNode* p; //在已经处理完毕的链表中,当前的遍历节点的上一个节点
        ListNode* q; 在已经处理完毕的链表中,当前节点
        ListNode* t;待比较处理的接待你
        while(head)
        {
            p = &temp; //当前个节点
            q = p->next; //下一个节点
            //将待比较的结点赋值给t
            t  = head;
            //移动head ,下次再次将head赋值给t时候就是下一个元素
            head = head->next;
            //寻找t在处理完毕链表中,后一个元素比它大的位置,将t插入到找到元素的前面位置
            while(q && q->val < t->val)
            {
                p = p->next;
                q = q->next;
            }
            t->next = q; //将位置q后的节点链接到t的后面
            p->next = t; //将tc出入到q的前面

        }
        return temp.next; //返回temp的下一个元素

    }
};

解题思路:

解题思路就是根据插入排序的思想，每次遍历都保证前n个数都是排好序的，那么按照原生的插入排序，是从当前元素前一个元素开始一个一个往前判断，只要比前面元素小，则往前移动，一直移动到有一个元素小于它或者移动到头部了则停止，这个位置就是当前元素在这一趟中应该在的位置。但是链表中不好往前移，只能每次都从头部开始往后判断，一直找到第一个比当前元素大的元素停止，然后调整一下指针，就是让当前元素插入到本趟合适的位置。由于有可能要与第一个元素交换，所以搞一个虚拟头节点处理起来会简单一点。

参考Java实现:
链接：https://www.nowcoder.com/questionTerminal/152bc6c5b14149e49bf5d8c46f53152b?f=discussion
来源：牛客网

class Solution {
    public ListNode insertionSortList(ListNode head) {
        //1.判断一下
        if(head == null || head.next == null){
            return head;
        }
        //2.新建一个虚拟节点，后面要用
        ListNode dummy = new ListNode(0);
        //3.curr指向的节点及其后面所有节点都是未排序的，前面的都是排好序的
        ListNode curr = head;
        while(curr != null){
            //4.每次循环，pre都重新指向dummy，dummy后一个节点到curr前一个节点都是排好序的
            ListNode pre = dummy;
            //5.保存一下当前节点后面一个节点的引用
            ListNode next = curr.next;
            //6.每次都从dummy节点下一个开始找，前面都是排好序的，如果小于当前节点则指针后移，一直找到pre.next为空
            //或者比当前节点大的时候，停止，表明pre的下一个节点就是当前节点应该放的位置
            while(pre.next != null && pre.next.val < curr.val){
                pre = pre.next;
            }
            //7.找到当前节点应该放的位置之后，下面的工作就是移动指针，让curr插到pre和pre.next中间
            //然后让curr后移一位，前面都是排好序的
            curr.next = pre.next;
            pre.next = curr;
            curr = next;
        }
        //8.dummy后面就是我们所需要的用插入排序排好序的链表
        return dummy.next;
    }
}