One question per day

Give the order the head of a linked list  head , Use Insertion sort Sort the list , And back to   The header of the sorted linked list  .

Insertion sort   The steps of the algorithm :

The insertion sort is iterative , Move only one element at a time , Until all elements can form an ordered output list .
In each iteration , Insert sort removes only one element to be sorted from the input data , Find its place in the sequence , And insert it into .
Repeat until all input data is inserted .
The following is a graphical example of the insertion sorting algorithm . Partially sorted list ( black ) Initially, only the first element in the list is included . Each iteration , Delete an element from the input data ( Red ), And insert in place into the sorted list .

Insert and sort the linked list .

Example 1：

Input : head = [4,2,1,3]
Output : [1,2,3,4]
Example  2：

Input : head = [-1,5,3,4,0]
Output : [-1,0,3,4,5]
 

Tips ：

The number of nodes in the list is  [1, 5000] Within the scope of
-5000 <= Node.val <= 5000

/**
 * 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 || head.next == null)
            return head;
        
        ListNode newhead = new ListNode(0);
        newhead.next = head;
        
        ListNode pre = newhead;    // The previous node of the insertion position 
        ListNode cur = head;       // Current node to insert 
        ListNode p = newhead, q = cur;    //p、q Respectively represent the current node cur Before 、 Back node 
        while(cur != null) {
            q = cur.next;
            pre = newhead;
            while(pre.next != null && pre.next.val < cur.val)    // Find the insertion location 
                pre = pre.next;
            if(pre.next == cur)
                p = p.next;
            else {
                cur.next = pre.next;
                pre.next = cur;
                p.next = q;
            }
            cur = q;
        }
        return newhead.next;
    }
}