Insertion Sort List（連結清單插入排序）

Sort a linked list using insertion sort.

這裡給單連結清單進行插入排序，個人想到兩種方法 一種是交換節點的指針，一種是交換節點的值，前者要判斷頭節點，感覺比較麻煩，就用了交換值的方法， 通常的插入排序是在插入點的位置依次與前面的元素相比較，如果比前面的小，就把目前的位置的值變成前一個位置的值，最後得到的是最終插入位置， 這裡單連結清單沒辦法往前搜尋，那麼就從頭開始搜尋， 如果發現目前位置的值比插入位置大，那麼就直接交換兩個節點的值，然後把後面所有節點的值後移即可。

class Solution
{
public:
    ListNode *insertionSortList(ListNode *head)
    {
        if (head == NULL || head->next == NULL) return head;
        ListNode *tmp, *ptr_i = head, *ptr_j;
        int tval = 0;
        while (ptr_i)
        {
            tmp = head;
            ptr_j = ptr_i->next;
            while (ptr_j && tmp != ptr_j)
            {
                // 如果tmp指向的位置的值大于ptr_j的值 則交換并把所有tmp後面的資料後移
                if (ptr_j->val < tmp->val)
                {
                    //下列三行交換值
                    tval = tmp->val;
                    tmp->val = ptr_j->val;
                    ptr_j->val = tval;
                    //下面的while循環将tmp後面的節點值依次後移，類似數組的插入後移動
                    while (tmp != ptr_j)
                    {
                        tval = ptr_j->val;
                        ptr_j->val = tmp->next->val;
                        tmp->next->val = tval;
                        tmp = tmp->next;
                    }
                    break;
                }
                else
                    tmp = tmp->next;
            }
            ptr_i = ptr_i->next;
        }
        return head;
    }
};