7ms Java solution with explanation
The only real modification here is to take advantage of the ability to add to both the front and end of a linked list in constant time.  A typical insertion sor
The only real modification here is to take advantage of the ability to add to both the front and end of a linked list in constant time.  A typical insertion sort would have to go through the entire array to find the new location to insert the element. If the element should be placed first in the array then we have to shift everything over.  Thankfully, with a linked list we don't need to do this.  The slight modification of keeping a pointer to the last node as well as the first dramatically increased the runtime of the algorithm.  That being said, the speedup still has a lot to do with the ordering if the items in the array.  \n\n    public ListNode insertionSortList(ListNode head) {\n        if (head == null || head.next == null)\n        {\n            return head;\n        }\n\n        ListNode sortedHead = head, sortedTail = head;\n        head = head.next;\n        sortedHead.next = null;\n        \n        while (head != null)\n        {\n            ListNode temp = head;\n            head = head.next;\n            temp.next = null;\n            \n            // new val is less than the head, just insert in the front\n            if (temp.val <= sortedHead.val)\n            {\n                temp.next = sortedHead;\n                sortedTail = sortedHead.next == null ? sortedHead : sortedTail;\n                sortedHead = temp;\n            }\n            // new val is greater than the tail, just insert at the back\n            else if (temp.val >= sortedTail.val)\n            {\n                sortedTail.next = temp;\n                sortedTail = sortedTail.next;\n            }\n            // new val is somewhere in the middle, we will have to find its proper\n            // location.\n            else\n            {\n                ListNode current = sortedHead;\n                while (current.next != null && current.next.val < temp.val)\n                {\n                    current = current.next;\n                }\n                \n                temp.next = current.next;\n                current.next = temp;\n            }\n        }\n        \n        return sortedHead;\n    }
[]