Insertion Sort Linked List

InsertionSortLinkedList

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        
       if(head==null || head.next==null){
           return head;
       }
       ListNode newHead = null;
       while(head!=null){
           ListNode curr = head;
           head = head.next;
           if( newHead ==null || curr.val<newHead.val ){
               curr.next = newHead;
               newHead = curr;
           }else{
               ListNode p = newHead;
               while(p!=null){
                   if( p.next==null || curr.val<p.next.val ){
                       curr.next = p.next;
                       p.next = curr;
                       break;
                   }
                   p=p.next;
               }
           }
       }
       return newHead;
    }
}