> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/147.-insertion-sort-list-medium.md).

# 147. Insertion Sort List

## 1.問題 

* 用Insertion sort對linked list排序

![](/files/-LHM9MNKTofHCNGYt3t6)

## 2.想法 

* 提問
* 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: 
    * 將p移動到適當的位置: 當p->next->val > curr->val時停下來, 將curr插入p, p->next之間
* 測試計算複雜度

##  3.程式碼 

```
/**
 * 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;
    }
}
```