[leetcode] Insertion Sort List

题目链接： here。

题目描述：

　　Sort a linked list using insertion sort.

　　题目要求使用插入排序的方法来实现单链表的排序。插入排序是一种简单的排序，算法描述参考维基百科，或者《算法导论》。

　　下面是我实现的代码：

 1 /**
 2     Author: Vincent Zhang
 3     Problem: https://oj.leetcode.com/problems/insertion-sort-list/
 4 */
 5 class Solution {
 6 public:
 7     ListNode *insertionSortList(ListNode *head) {
 8 
 9         // check if head is NULL or has no next node, return head
10         if (head == NULL || head->next == NULL) return head;
11 
12         // pointer point to current node
13         ListNode *pCurrent = head->next;
14         // set the next node of head to NULL, which break the inputed list into 2 halves;
15         // first half begin with head, end with a NULL: the sorted part;
16         // second half contains the unsorted nodes.
17         head->next = NULL;
18         ListNode *pTemp = NULL, *index = NULL;
19         // pCurrent is not NULL, meaning not the last node
20         while (pCurrent != NULL)
21         {   
22             // save the next node of pCurrent to pTemp
23             pTemp = pCurrent->next;
24             // insertion to the head
25             if (pCurrent->val <= head->val)
26             {
27                 pCurrent->next = head;
28                 head = pCurrent;
29             }
30             else    // Find the proper position to insert
31             {
32                 index = head;
33                 while (index->next !=NULL && pCurrent->val > index->next->val)
34                     index = index->next;
35                 pCurrent->next = index->next;
36                 index->next = pCurrent;
37             }
38             pCurrent = pTemp;
39         }
40         return head;
41     }
42 };

View Code

　　这里，我的思路是，一开始，将链表断开，一段是排好序的，另一段是未排序的，然后每次把未排序的链表的头节点插入到排好序的链表中合适的位置。一开始在实现的时候，没有贯彻把链表断开的思想，导致出现了一些不可预计的BUG。下面是几个关键点：

将链表断成两节；
插入的时候单独考虑插入到头节点之前的情况；
保存待排序的第二个节点，因为第一个节点插入到已排序的链表后就和未排序的链表断开了；
插入的时候注意寻找合适的插入位置，因为是单链表，不能方便的逆向访问；

　　如果觉得博文对您有用，请推荐；转发请注明出处，谢谢。