Insertion Sort List

Insertion Sort List

 Sort a linked list using insertion sort.

-------------------------------------- thinking ----------------------------------------------------------------
1. be very careful about the updating of cur and pre
2. be very careful when to terminate the while loop!
-------------------------------------- codes --------------------------------------------------------------------
/**
 * 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 == NULL) {
            return head;
        }
        ListNode *pre = head;
        ListNode *cur = head->next;
        if (cur == NULL) {
            return head;
        }
        ListNode *next = cur->next;
        while (cur) {
            //compare from head to pre
            ListNode *com = head;
            ListNode *pre_com = NULL;
            next = cur->next;
            while (com != cur) {
                if (cur->val < com->val) {
                    //delete cur and insert it before com
                    ListNode *tmp = cur;
                    //bug here!!!
                    cur = pre;
                    delNode(pre, tmp);
                    if (pre_com == NULL) {
                        tmp->next = head;
                        head = tmp;
                    } else {
                        tmp->next = pre_com->next;
                        pre_com->next = tmp;
                    }
                    //bug here
                    if (next == NULL) {
                        return head;
                    }
                    break;
                }
                pre_com = com;
                com = com->next;
            }
            pre = cur;
            cur = next;
        }
        return head;
    }
    void delNode(ListNode *pre, ListNode *cur) {
        pre->next = cur->next;
        cur->next = NULL;
    }
};