[LeetCode] 147. Insertion Sort List 解题思路

 1     void insertSort(ListNode* p1, ListNode* p2){
 2         ListNode* next2 = p2->next;
 3         p2->next = p2->next->next;
 4         next2->next = p1->next;
 5         p1->next = next2;
 6     }
 7     
 8     ListNode* insertionSortList(ListNode* head) {
 9         
10         if (head == NULL){
11             return head;
12         }
13         
14         ListNode* r = head;
15         
16         while(r->next != NULL){
17             ListNode* l = new ListNode(0);
18             l->next = head;
19             while(l != r){
20                 if (l->next->val > r->next->val){
21                                     
22                     if (l->next == head) {
23                         head = r->next;                        
24                     }
25 
26                     insertSort(l, r);        
27                     break;
28                 }
29                 l = l->next;
30             }
31             
32             if (r->next != NULL && r->next->val >= r->val) {
33                 r = r->next;
34             }
35         }
36         
37         return head;
38     }