Insertion Sort List

Sort a linked list using insertion sort.

Basic question.

//Should I solve this problem in place?
//Contains duplicates values?

/**
 * 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 * re = NULL;
        while(head != NULL){
            //first step
            if(re == NULL){
                re = head;
                head = head->next;
                re->next = NULL;
            }
            else{
                ListNode * next = head->next;
                ListNode * prev = NULL;
                for(ListNode * p = re; p != NULL; p = p->next){
                    if(p->val > head->val){
                        break;
                    }
                    prev = p;
                }
                if(prev == NULL){
                    head->next = re;
                    re = head;
                }
                else{
                    head->next = prev->next;
                    prev->next = head;
                }
                head = next;
            }
        }
        return re;
    }
};