Insertion Sort List. Sort a linked list using insertion sort..

insertion_sort_linked_list.cpp

/**
 * 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 * newHead = NULL;
        while(head) {
            ListNode *next = head->next;
            head->next = NULL;  //cut off 
            if (!newHead) {
                newHead = head;
            }
            else {
                ListNode * prev = NULL;
                ListNode * scan = newHead;
                while(scan && scan->val <= head->val) {
                    prev = scan;
                    scan = scan->next;
                }
                //scan->val  > head->val
                // newHead -> ...  -> head -> scan 
                if (prev) {
                    prev->next = head;
                    head->next = scan;
                }
                else { //prev=NULL, head -> scan
                    head->next = newHead;
                    newHead = head;
                }
            }
            head = next;
        }
        return newHead;
    }
};