题目描述

对链表进行插入排序。

样例

示例 1：

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

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

算法1

模拟

清晰易懂 见注释

C++ 代码

/*

思路：将原链表的所有节点遍历一次，将每一个节点插入到新的链表的对应位置中。

新链表的头结点为dummy

*/
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {

             ListNode *dummy = new ListNode(0); 

             ListNode *cur=  head; //当前遍历的点从head开始

             ListNode *pre = dummy;//pre指的是已经遍历过的部分，也就是已经从原链表截取下来拼接到新的虚拟头结点的部分。大概是这个意思，继续往下看。

             ListNode *next = nullptr; //预存cur的next指针,防止被覆盖了以后找不到了。

             while(cur != nullptr)
             {
                 while(pre->next && pre->next->val <= cur->val) pre = pre->next;
                 //因为用了虚拟头结点，第一个节点的值不能用，所以要从pre->next开始检查。
                 //新的链表依次遍历已经存在的节点，如果该节点的值小于等于cur->val,就继续向后遍历,直到找到能插入的位置停下来

                 next = cur->next; //预存一下cur的next指针

                 cur->next = pre->next; //以下两行将cur节点接到了新的链表中的对应位置

                 pre->next = cur;

                 cur = next; // cur向后遍历一个，取原先保留的cur->next指针的值

                 pre = dummy; // 将pre回退到dummy的位置,便于下一次遍历和比较，然后再插入，如此反复。


             }
             return dummy->next;
    }
};