# 147-Insertion Sort List
###### tags: `Medium`
## Question
https://leetcode.com/problems/insertion-sort-list/
## Key
## Reference
## Solution

class Solution {
public:
     ListNode *insertionSortList(ListNode *head) {
        if(head == NULL || head->next == NULL) {
            return head;
        }

        ListNode* dummy = new ListNode(0);

        ListNode* p = dummy;

        ListNode* cur = head;
        while(cur)
        {
            p = dummy;
            //compare and move to next  node
            while(p->next && p->next->val <= cur->val) 
            {
                p = p->next;
            }

            //先把原來的值存到n(較大) 再更新成current(較小)
            ListNode* n = p->next;
            p->next = cur;
            //next insertion node
            cur = cur->next;
            //存下個點才不會因NULL而跳出loop
            p->next->next = n;
        }

        return dummy->next;
    }
};