題目147. Insertion Sort List

Sort a linked list using insertion sort.

public class Solution {
    public ListNode insertionSortList(ListNode head) {
       if(head == null || head.next == null){
            return head;
        }
        
        ListNode tempHead = new ListNode(1);
        ListNode node = head.next;
        tempHead.next = head;
        tempHead.next.next = null;
        
        
        ListNode preNode = null;
        ListNode tempNode = null;
        ListNode tempNextNode = null;
        while(node != null){
            tempNextNode = node.next;
            int val = node.val;
            preNode = tempHead;
            tempNode = tempHead.next;
            while(tempNode != null){
                if(val > tempNode.val){
                    preNode = tempNode;
                    tempNode = tempNode.next;
                }else{
                    node.next = preNode.next;
                    preNode.next = node;
                    break;
                }
            }
            if(tempNode == null){
                node.next = preNode.next;
                preNode.next = node;
            }
            node = tempNextNode;
        }
        return tempHead.next;
    }
}