# 147. Insertion Sort List

## 1.問題 

* 用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.想法 

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jenhsuan.gitbook.io/algorithm/leetcode/147.-insertion-sort-list-medium.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.