insertion sort list

struct  {
  bool operator() (const ListNode* lhs, const ListNode* rhs) const
  {return lhs->val < rhs->val;}
};  
class Solution {
public:
    set<ListNode*, classcomp>  labels ; 
    ListNode* insertionSortList(ListNode* head) {
            while(head){
                labels.insert(head); 
                head = head->next ;
            }
     
            head = labels[0]; 
            ListNode* node = labels[0]; 
            for(int i=1; i<labels.size(); i++){
                node->next =  labels[i]; 
                node = node->next ; 
            }
            
            return head; 
    }
};
``` 
basically `unordered_set` has ordering by default, so how about first inserting each element from the list to set, then set the next pointer for each element, which take additional space, but did the job straight forward 
#
since single linked list can't access the previous node, so define prev pointer and current pointer, and every insertaion needs do the compare from frist element to the previous element. 
```c 
public class Solution {
  public  ListNode *insertionoSortList(ListNode *head){
    ListNode *result = nullptr ;
    if(head == nullprt || head.next = null){
      result = head ;
      return result ;
    }
    ListNode *dummy = new ListNode(0); 
    ListNode *cur = head ; 
    ListNode *next, *pre;
    while(cur != nullptr){
        next = cur->next ;
        pre = dummy ; 
        while(pre.next != nullptr && pre.next->val <  cur->val){
          pre = pre.next ; 
        }  
        cur->next = pre->next ; 
        pre->next = cur ; 
        cur = next ; 
      }       
    }