leetcode

题目：Insertion Sort List

Sort a linked list using insertion sort.

题目比较简单，就是对链表进行插入排序

个人思路：

1，用插入排序的方法来解就行，注意链表的处理，可以给原链表加个头结点来使得处理统一（我的代码没有加，懒得改了）

代码：

 1 #include <stddef.h>
 2 
 3 struct ListNode
 4 {
 5     int val;
 6     ListNode *next;
 7     ListNode(int x) : val(x), next(NULL) {};
 8 };
 9 
10 class Solution {
11 public:
12     ListNode *insertionSortList(ListNode *head) {
13         if (!head)
14         {
15             return NULL;
16         }
17 
18         ListNode *current = head->next;
19         ListNode *currentBefore = head;
20         ListNode *find = NULL;
21         ListNode *findBefore = NULL;
22 
23         while (current)
24         {
25             find = head;
26             while (find != current)
27             {
28                 if (current->val < find->val)
29                 {
30                     if (find == head) //当前结点小于头结点
31                     {
32                         currentBefore->next = current->next;
33                         current->next = find;
34                         head = current;
35                         current = currentBefore->next;
36                         break;
37                     }
38                     else
39                     {
40                         currentBefore->next = current->next;
41                         current->next = find;
42                         findBefore->next = current;
43                         current = currentBefore->next;
44                         break;
45                     }
46                 }
47                 findBefore = find;
48                 find = find->next;
49             }
50             if (find == current) //当前结点比前面结点都大，没有对链表做任何改变
51             {
52                 currentBefore = current;
53                 current = current->next;
54             }
55         }
56 
57         return head;
58     }
59 };

View Code

网上的思路基本是一样的