# 147. Insertion Sort List

## 1.問題&#x20;

* 用Insertion sort對linked list排序

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LHM5PY133NAmbY-imiS%2F-LHM9MNKTofHCNGYt3t6%2F2018071402.jpg?alt=media\&token=a0499328-651a-4aaf-872f-5a14e3077d0d)

## 2.想法&#x20;

* 提問
* function header, parameter
* test input
* 觀察
* 說明想法
  * 碰到需要一面前進, 一面從頭找適當位置情形, 通常需要一個dummy node (p)
  * 分成兩段list: p (sort過的list), sort中的list
  * sort中的list: curr指向head後, 讓head = head->next, 因為curr將會移到p list
  * sort過的list:&#x20;
    * 將p移動到適當的位置: 當p->next->val > curr->val時停下來, 將curr插入p, p->next之間
* 測試計算複雜度

## &#x20;3.程式碼&#x20;

```
/**
 * 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) {
            return NULL;
        }
        
        ListNode* newNode = new ListNode(0);
        while (head) {
            ListNode* curr = head;
            head = head->next;
            //回到原點
            ListNode* pre = newNode;
            //移動pre到適當位置: 盡可能移動到小於curr的, list的最右端
            while (pre->next && pre->next->val <= curr->val) {
                pre = pre->next;
            }
            curr->next = pre->next;
            pre->next = curr;
        }
        
        head = newNode->next;
        delete newNode;
        return head;
    }
}
```



