147. Insertion Sort List

其實, 就是insertion sort, 不過換成用linked list, 有點生疏

我們會另外開一個node, 然後開始針對另外一個陣列的節點慢慢插入

在每次輪尋中, 把新的串列的指針都移回最前面從新找可能大於目標的節點

在array可以用inplace, 在這邊要達成同樣的概念需要熟悉操作linkedlist

class Solution {
  public:
    ListNode *insertionSortList(ListNode *head) {
        ListNode *dummy = new ListNode(-1);
        ListNode *cur = dummy;
        while (head) {
            ListNode *t = head->next;
            cur = dummy;
            while (cur->next && cur->next->val <= head->val) {
                cur = cur->next;
            }
            head->next = cur->next;
            cur->next = head;
            head = t;
        }
return dummy->next;
    }
};