LeetCode:Insertion Sort List

题目链接链表的插入排序

Sort a linked list using insertion sort.

建议：为了操作方便，添加一个额外的头结点。代码如下：本文地址

 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         // IMPORTANT: Please reset any member data you declared, as
13         // the same Solution instance will be reused for each test case.
14         if(head == NULL || head->next == NULL)return head;
15         ListNode *p = head->next, *pstart = new ListNode(0), *pend = head;
16         pstart->next = head; //为了操作方便，添加一个头结点
17         while(p != NULL)
18         {
19             ListNode *tmp = pstart->next, *pre = pstart;
20             while(tmp != p && p->val >= tmp->val)
21                 {tmp = tmp->next; pre = pre->next;}
22             if(tmp == p)pend = p;
23             else
24             {
25                 pend->next = p->next;
26                 p->next = tmp;
27                 pre->next = p;
28             }
29             p = pend->next;
30         }
31         head = pstart->next;
32         delete pstart;
33         return head;
34     }
35 };