package InsertionSortList;

/**
 * Definition for singly-linked list.
 */
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

/**
 * Sort a linked list using insertion sort.
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null)
            return null;
        ListNode nh = head;
        head = head.next;
        nh.next = null;

        while (head != null) {
            if (head.val < nh.val) {
                ListNode next = head.next;
                head.next = nh;
                nh = head;
                head = next;
                continue;
            }
            ListNode p = nh;
            boolean inserted = false;
            while (p.next != null) {
                if (head.val < p.next.val) {
                    ListNode next = head.next;
                    ListNode pnext = p.next;
                    p.next = head;
                    head.next = pnext;
                    head = next;
                    inserted = true;
                    break;
                }
                p = p.next;
            }
            if (!inserted) {
                p.next = head;
                head = head.next;
                p.next.next = null;
            }
        }
        return nh;
    }
}
@@ -234,16 +234,17 @@
 ution %7B%0A
+%0A
     publ
@@ -480,32 +480,79 @@
 val %3C nh.val) %7B%0A
+                // Insert before the head node%0A
                 
@@ -751,115 +751,366 @@
     
-boolean inserted = false;%0A            while (p.next != null) %7B%0A                if (head.val %3C p.next.val) %7B
+while (true) %7B%0A                if (p.next == null) %7B%0A                    // Insert after the tail node%0A                    p.next = head;%0A                    head = head.next;%0A                    p.next.next = null;%0A                    break;%0A                %7D%0A                if (head.val %3C p.next.val) %7B%0A                    // Insert in the middle of list 
 %0A   
@@ -1309,45 +1309,8 @@
 xt;%0A
-                    inserted = true;%0A
     
@@ -1396,152 +1396,8 @@
   %7D%0A
-            if (!inserted) %7B%0A                p.next = head;%0A                head = head.next;%0A                p.next.next = null;%0A            %7D%0A
     

Simplify insertion sort list