对链表进行插入排序

思路

思路很简单：链表insert+插入排序。主要在于考察编程基本功，雷弟说指着指着就指到姥姥家了。。。

• 设置哑节点便于操作头指针，newbie可以参考这篇博文，pre指针每次从头遍历，和待插入元素比较大小，小于则一直往后直到找出下一个节点大于待查节点的元素即插入点
• 链表插入，解释略
• pre，cur返回现场，继续任务。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head==null) return null;
        ListNode dummy = new ListNode(-1);
        //cur用来遍历原始链表
        ListNode cur = head;
        //pre用来记录待插元素的前一个节点
        ListNode pre = dummy;
        while(cur!=null){
            //遍历新链表，若节点元素小于待插入元素则继续,直到找到应插之处的前面一个节点
           while(pre.next!=null&&pre.next.val<cur.val) pre = pre.next;
           //插入
           ListNode save = cur.next;
           cur.next = pre.next;
           pre.next = cur;
           //因为每次pre都要从头比较待插元素
           pre=dummy;
           //cur继续遍历，断了的线继续连QAQ
           cur=save  ;
        }
        return dummy.next;
    }
}

本文地址：https://blog.csdn.net/dtzly/article/details/109913931