[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          if (head == NULL || head->next == NULL) {
13         return head;
14     }
15     ListNode *h = new ListNode(0);
16     h->next = head;
17     ListNode *p, *q, *tmp;
18     bool flag;
19     for (p = head; p->next != NULL;) {
20         flag = false;
21         for (q = h; q != p; q = q->next) {
22             if (p->next->val < q->next->val) {
23                 tmp = p->next;
24                 p->next = tmp->next;
25                 tmp->next = q->next;
26                 q->next = tmp;
27                 flag = true; break;
28             }
29         }
30         if (!flag) p = p->next;
31     }
32     head = h->next;
33     delete h; h = NULL;
34     return head;
35     }
36 };