Problem:
Sort a linked list using insertion sort.
分析：
当链表长度小于等于1时，直接返回结果。当长度超过1时，从第二个节点开始循环查看链表中的每个节点，但因为还需要遍历当前节点之前有序的子链表，找到合适的位置插入当前节点，插入后还需要接上链表，所以需要存储当前考察节点的前一个节点的指针。分三种情况：情况一，如果当前考察节点比有序表中的第一个节点的值都小，那么直接将其插入表头，并用当前节点的前一个节点指针接好链表，然后指针后移考察下一个；情况二，如果当前考察节点在有序表中间，那么需要将其插入对应位置，同时用当前节点的前一个节点指针接好链表，前一个指针不变，当前指针后移；情况三，如果当前考察节点在有序表的末尾，则只需将前一个指针与当前指针都后移即可。
1 class Solution { 2 public: 3 ListNode *insertionSortList(ListNode *head) { 4 if(head == NULL || head->next == NULL) { 5 return head; 6 } 7 8 ListNode *pre = head, *cur = head->next; 9 while(cur != NULL) { 10 // case1 11 if(head->val > cur->val) { 12 pre->next = cur->next; 13 cur->next = head; 14 head = cur; 15 } else { 16 ListNode *p = head, *q = head->next; 17 while(q != cur && p->val < cur->val && q->val < cur->val) { 18 p = p->next; 19 q = q->next; 20 } 21 22 if(q != cur) { // case 2 23 pre->next = cur->next; 24 cur->next = q; 25 p->next = cur; 26 } else { // case3 27 pre = pre->next; 28 } 29 } 30 31 cur = pre->next; 32 } 33 return head; 34 } 35 };
Insertion Sort List,布布扣,bubuko.com
原文：http://www.cnblogs.com/foreverinside/p/3695757.html