Explained C++ solution (24ms)
Keep a sorted partial list (head) and start from the second node (head -> next), each time when we see a node with val smaller than its previous node, we scan f
Keep a sorted partial list (`head`) and start from the second node (`head -> next`), each time when we see a node with `val` smaller than its previous node, we scan from the `head` and find the position that the node should be inserted. Since a node may be inserted before `head`, we create a `dummy` head that points to `head`.\n\n```cpp\n/**\n * Definition for singly-linked list.\n * struct ListNode {\n *     int val;\n *     ListNode *next;\n *     ListNode(int x) : val(x), next(NULL) {}\n * };\n */\nclass Solution {\npublic:\n    ListNode* insertionSortList(ListNode* head) {\n        ListNode* dummy = new ListNode(0);\n        dummy -> next = head;\n        ListNode *pre = dummy, *cur = head;\n        while (cur) {\n            if ((cur -> next) && (cur -> next -> val < cur -> val)) {\n                while ((pre -> next) && (pre -> next -> val < cur -> next -> val)) {\n                    pre = pre -> next;\n                }\n                ListNode* temp = pre -> next;\n                pre -> next = cur -> next;\n                cur -> next = cur -> next -> next;\n                pre -> next -> next = temp;\n                pre = dummy;\n            }\n            else {\n                cur = cur -> next;\n            }\n        }\n        return dummy -> next;\n    }\n};\n```
['Linked List', 'C++']