题目：
Sort a linked list using insertion sort.
代码：
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* insertionSortList(ListNode* head) { ListNode *p1 = head; ListNode dummy(INT_MIN); while (p1) { ListNode *tmp1 = p1->next; ListNode *p2 = &dummy; while ( p2->next ) { if ( p2->next->val > p1->val ) { ListNode *tmp2 = p2->next; p2->next = p1; p1->next = tmp2; break; } else { p2 = p2->next; } } if (!p2->next) { p2->next = p1; p1->next = NULL; } p1 = tmp1; } return dummy.next; }}; tips：
插入排序算法在链表上的实现。
1. 设立一个虚表头dummy，虚表头后面接的就是已经排序好的部分ListNodes
2. 维护一个指针p1，始终指向待插入的ListNode
3. 里层的while循环需要选择插入的具体位置
=============================================
第二次过这道题，一次AC。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* insertionSortList(ListNode* head) { ListNode dummpy(INT_MIN); while ( head ) { ListNode* tmp = head->next; ListNode* pre = &dummpy; ListNode* curr = dummpy.next; while ( curr ) { if ( head->val val) { pre->next = head; head->next = curr; break; } else { pre = curr; curr = curr->next; } } if ( !curr ) { pre->next = head; head->next = NULL; } head = tmp; } return dummpy.next; }};