【LeetCode题解】147. 对链表进行插入排序

对链表进行插入排序。插入排序算法插入排序是迭代的每次只移动一个元素直到所有元素可以形成一个有序的输出列表。每次迭代中插入排序只从输入数据中移除一个待排序的元素找到它在序列中适当的位置并将其插入。重复直到所有输入数据插入完为止。题解用[ pre, cur, post]遍历整个链表取出cur将pre与cur中间截断【因为无指针比较如果pre直接与post连接无法选择合适地点中止cur遍历cur是不应该插入到post之后的】cur与post中间截断从链表头开始将每个结点与cur的值进行比较找到cur的插入位置分为前表(start 到 pre)尾(即pre之后原位置这种情况跳过即可)或前表中间部分将前表与后表进行连接继续循环class Solution { public ListNode insertionSortList(ListNode head) { if(headnull || head.nextnull){ return head; } ListNode start new ListNode(-1); start.next head; //cur为当前待插入结点pre为cur前结点 ListNode cur head; ListNode pre head; cur pre.next; //post记录截断后带插入cur结点后续结点 ListNode post null; while(pre!null cur!null){ if(cur.valpre.val){ //cur当前有序 cur cur.next; pre pre.next; continue; } post cur.next; pre.next null; cur.next null; ListNode tmp start; while(tmp.next!null tmp.next.valcur.val){ tmp tmp.next; } //已找到位置插入 cur.next tmp.next; tmp.next cur; //定位新pre并连接post pre.next post; cur pre.next; } return start.next; } }