[牛客经典必刷算法题] LC5-链表的插入排序

输入
{30,20,40}
 
返回值
{20,30,40}

import java.util.*;

/* * public class ListNode { * int val; * ListNode next = null; * } */

public class Solution { 
   
    /** * * @param head ListNode类 * @return ListNode类 */
    public ListNode insertionSortList (ListNode head) { 
   
        if(head == null || head.next == null) return head;
        // 虚节点
        ListNode dummy = new ListNode(-1), pre;
        dummy.next = head;
        
        while(head != null && head.next != null){ 
   
            // 如果小于下一节点，直接跳过，加速排序
            if(head.val <= head.next.val){ 
   
                head = head.next;
                continue;
            }
            
            // 寻找当前节点正确位置
            pre = dummy;
            while(pre.next.val < head.next.val) pre = pre.next;
            // 取出当前节点curr
            ListNode curr = head.next;
            //保存下一节点
            head.next = curr.next;
            // 插入操作
            curr.next = pre.next;
            pre.next = curr;
        }
        return dummy.next;
    }
}