insertion sort list

Posted on |

leetCode 147, this is another example when solving problem, either find a good data structure, which looks like stand in a higher dimensions with additional DOF, or define the routines on the given data structure.

additional set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
struct classcomp {
  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 
## single linked list
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 ; 
        }  //return the position where cur node should insert 
        cur->next = pre->next ; 
        pre->next = cur ; 
        cur = next ; 
      }       
    }