[LeetCode] Insertion Sort List

Sort a linked list using insertion sort.

思路：
拿出原list的头节点，用一个指针扫描新list直到找到插入位置，并插入。注意点：
1. 用dummy head来简化新list的头节点操作。
2. 由于插入节点需要依赖插入位置的前一节点。所以用指针p来查找新list节点时，始终用p->next来和要插入的节点比较，而不是用p来比较。
3. 注意当节点需要插入新list尾部的情况。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

class Solution { public: ListNode *insertionSortList(ListNode *head) { ListNode *newHead = new ListNode(INT_MIN); while(head) { ListNode *cur = head; ListNode *p = newHead; head = head->next; while(p->next && p->next->val<=cur->val) p = p->next; cur->next = p->next; p->next = cur; } head = newHead->next; delete newHead; return head; } };