An easy and clear way to sort ( O(1) space )
public ListNode insertionSortList(ListNode head) {\n    \t\tif( head == null ){\n    \t\t\treturn head;\n    \t\t}\n    \t\t\n    \t\tListNode helper = new List
    public ListNode insertionSortList(ListNode head) {\n    \t\tif( head == null ){\n    \t\t\treturn head;\n    \t\t}\n    \t\t\n    \t\tListNode helper = new ListNode(0); //new starter of the sorted list\n    \t\tListNode cur = head; //the node will be inserted\n    \t\tListNode pre = helper; //insert node between pre and pre.next\n    \t\tListNode next = null; //the next node will be inserted\n    \t\t//not the end of input list\n    \t\twhile( cur != null ){\n    \t\t\tnext = cur.next;\n    \t\t\t//find the right place to insert\n    \t\t\twhile( pre.next != null && pre.next.val < cur.val ){\n    \t\t\t\tpre = pre.next;\n    \t\t\t}\n    \t\t\t//insert between pre and pre.next\n    \t\t\tcur.next = pre.next;\n    \t\t\tpre.next = cur;\n    \t\t\tpre = helper;\n    \t\t\tcur = next;\n    \t\t}\n    \t\t\n    \t\treturn helper.next;\n    \t}
['Java']