如果那天前先做了这道题就好了。。言归正传，需要两个dummy节点，本质上就是从原来的链表中删除最小的，加到新的链表中去。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 |
class
Solution {public: ListNode *insertionSortList(ListNode *head) { ListNode *o_dummy = new
ListNode(0); ListNode *n_dummy = new
ListNode(0); o_dummy->next = head; ListNode *last = n_dummy; while
(o_dummy->next != NULL) { ListNode *prev = o_dummy; ListNode *node = prev->next; // find node with min val ListNode *min_node = node; ListNode *prev_node = prev; while
(node != NULL) { if
(node->val < min_node->val) { min_node = node; prev_node = prev; } node = node->next; prev = prev->next; } prev_node->next = min_node->next; // insert to new list min_node->next = NULL; last->next = min_node; last = min_node; } return
n_dummy->next; }}; |
原文：http://www.cnblogs.com/lautsie/p/3546609.html