No.147 Insertion Sorted List

No.147 Insertion Sorted List

Sort a linked list using insertion sort.

单链表排序：使用插入排序

时间复杂度是排序算法的O(n^2)，空间复杂度是O(1)

难度：无他，把思路理顺，注意细节，并测试一下；另外头结点的巧妙应用，int最小表示方式!!

 1 #include "stdafx.h"
 2 #include <limits>
 3 using namespace std;
 4 
 5 struct ListNode
 6 {
 7     int val;
 8     ListNode *next;
 9     ListNode(int x):val(x),next(NULL){}
10 };
11 class Solution
12 {
13 public:
14     ListNode* insertionSortList(ListNode *head)
15     {//单链表排序：使用插入排序
16         if(head == NULL || head->next == NULL)
17             return head;
18 
19         ListNode help(numeric_limits<int>::min());//创建头结点！！！
20         help.next = head;//!!!
21 
22         ListNode *current;//记录当前要排序的节点
23         current = head->next;
24         head->next = NULL;
25 
26         ListNode *tmp, *p;
27         while(current)
28         {
29             //从头到尾依次遍历以插入数据
30             //tmp = help.next;
31             tmp = &help;
32             while(tmp && (tmp->val < current->val))
33             {
34                 if((tmp->next) && (tmp->next->val < current->val))
35                     tmp = tmp->next;
36                 else
37                     break;//找到插入位置
38             }
39             
40             p = current->next;
41             current->next = tmp->next;
42             tmp->next = current;
43             current = p;
44         }
45 
46         return help.next;
47     }
48 };