LeetCode----Insertion sort list

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode *list)
    {
        ListNode *new_list(NULL), *next(NULL);
        while(list)
        {
            next = list->next;
            new_list = InsertNode(new_list, list);
            list = next;
        }
        return new_list;
    }
private:
    ListNode* InsertNode(ListNode *list, ListNode *node)
    {
        //insert node into a sorted list
        ListNode *pre(NULL), *cur(list);
        while(cur && cur->val < node->val)
        {
            pre = cur;
            cur = cur->next;
        }
        if(pre == NULL){
            node->next = cur;
            return node;
        }
        else{
            node->next = cur;
            pre->next = node;
        }
        return list;
    }
};

LeetCode----Insertion sort list

原文：http://blog.csdn.net/shoulinjun/article/details/19290271