147. Insertion Sort List题解
题目描述：
Sort a linked list using insertion sort.
题目链接：147. Insertion Sort List
算法描述：
题目很简单，一句话，对一个链表进行排序（默认为从小到大），返回排序好的链表。
解法很直接，我们构造一个返回链表 ansLink （存储已经排序好的链表），每次循环针对原链表的首元素，当原链表 head 的首元素找到在 ansLink 中对应的位置后进行插入。
我们需要注意在原链表首元素的位置存储它的下一位 h ，以方便插入后顺利找到原链表。遍历结束的条件是原链表为空。最后我们返回 ansLink 的后一位。
代码：
/** * 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* ansLink = new ListNode(INT_MIN); while(head != NULL){ ListNode* h = head->next; ListNode* p = ansLink; while(p->next != NULL && p->next->val<head->val){ p = p->next; } head->next = p->next; p->next = head; head = h; } return ansLink->next; } };
