Leetcode 147: insertion linklist

Sort a linked list using insertion sort.

M1:

类似 array的insertion sort> 

但是改变了listnode 的value值。

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        //sanity check
        if (head == NULL || head->next == NULL) return head;
        ListNode* p = head;
        while (p->next) {
            int tmp = p->val;
            ListNode* p2 = p->next;
            ListNode* smallest = p;
            while (p2) {
                if (p2->val < smallest->val) {
                    smallest = p2;
                }
                p2 = p2->next;
            }
            p->val = smallest->val;
            smallest->val = tmp;
            p = p->next;
        }
        return head;
    }
};
M2：利用指针操作
1. 每次遍历链表找到比当前值大的数，就插入在当前node的前面；
2. 如果没有比当前值大的数就把当前值插入在链表最后。
3. 利用dummy node来简化链表头发生改变的corner case 
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        //sanity check
        if (head == NULL || head->next == NULL) return head;
        ListNode* dummy = new ListNode(0);
        ListNode* pre = dummy;
        ListNode* cur = head;
        while (cur->next) {
            ListNode* next = cur->next;
            pre = dummy;
            while (pre->next != NULL && pre->next->val <= cur->val) {
                pre = pre->next;
            }
            cur->next = pre->next;
            pre->next = cur;
            cur = next;
        }
        return dummy->next;
    }
};