单链表的插入排序

 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             ListNode *list = head;
13 
14     if (list == NULL || list->next == NULL)
15     {
16         return list;
17     }
18 
19     ListNode *p1 = list;
20     ListNode *p2 = p1->next;
21     ListNode *p3 = p2->next;
22 
23     if (p1->val > p2->val)
24     {
25         swap(p1->val, p2->val);
26     }
27 
28     while (p3 != NULL)
29     {
30         ListNode *temp = p3->next;
31 
32         if (p1->val > p3->val)
33         {
34             ListNode *tmp = p3;
35             while (p2->next != p3)
36                 p2 = p2->next;
37             p2->next = p3->next;
38             tmp->next = p1;
39             list=tmp;
40             p1 = list;
41             p2 = p1->next;
42             p3 = temp;
43         }
44         else
45         {
46             while (p2->val < p3->val)
47             {
48                 p1 = p1->next;
49                 p2 = p2->next;
50             }
51             if (p2 != p3)
52             {
53                     p1->next = p3;
54                     ListNode *tmp = p2;
55                     while (tmp->next != p3)
56                         tmp = tmp->next;
57                     tmp->next = p3->next;
58                     p3->next = p2;
59                     p1 = list;
60                     p2 = list->next;
61                     p3 = temp;
62             }
63             else
64             {
65                     p1 = list;
66                     p2 = list->next;
67                     p3 = temp;
68             }
69             
70         }
71         
72     }
73     return list;
74         
75     }
76 };