Insertion Sort List

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* insertionSortList(ListNode* head) {
12         if(head == nullptr)  return head;
13         if(head->next == nullptr) return head;
14 
15         ListNode* helper = new ListNode(-1);
16         
17         ListNode* cur= head;
18         ListNode* pre;
19         ListNode* next;
20 
21         while(cur){
22             next = cur->next;
23             pre = helper;
24             
25             while(pre->next != nullptr && pre->next->val < cur->val){
26                 pre = pre -> next;
27             }
28             
29             cur->next = pre->next;
30             pre->next = cur;
31             cur = next;
32         }
33         
34         head = helper->next;
35         delete helper;
36         return head;
37     }
38 };