147. Insertion Sort List

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) {
        if(!head || !head->next)    return head;

        ListNode dummy(-1);

        while(head){
            ListNode *prev = &dummy;
            //要插入的节点
            ListNode *cur = head;
            head = head->next;

            //找到插入的位置
            while(prev->next && prev->next->val < cur->val)     prev = prev->next;

            //将cur插入到prev的后面
            cur->next = prev->next;
            prev->next = cur；      
        }
        return dummy.next;
    }
};