###### tags: `Leetcode` `medium` `list` `sort` `python` `c++`

# 147. Insertion Sort List

## [題目連結:] https://leetcode.com/problems/insertion-sort-list/

## 題目:
Given the ```head``` of a singly linked list, sort the list using **insertion sort**, and return the sorted list's head.

The steps of the **insertion sort** algorithm:

Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.

At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there.

It repeats until no input elements remain.

The following is a graphical example of the insertion sort algorithm. The partially sorted list (black) initially contains only the first element in the list. One element (red) is removed from the input data and inserted in-place into the sorted list with each iteration.


## 解題想法:

* 將node由小到大排序:
* 每個node逐一檢查加入

## Python_Sol1:

#Insertion Sort List
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
    def insert(self,node):
        if self.next==None:
            self.next=ListNode(node)
        else:
            self.next.insert(node)
    def printList(self):
        head=self
        stack=[]
        while head:
            stack.append(head.val)
            head=head.next
        print(stack)

class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummy=ListNode(0)
        while head:
            cur=head #當前node
            pre=dummy 
            head=head.next #記錄下個起始點
            #決定cur應該插入在pre為首的哪個位置
            while pre.next and cur.val>pre.next.val:
                pre=pre.next
            cur.next=pre.next
            pre.next=cur
        return dummy.next

if __name__=='__main__':
    root = ListNode(4)
    root.insert(2)
    root.insert(1)
    root.insert(3)
    print("Old  :",end='') 
    root.printList() #Old  :[4, 2, 1, 3]

    result=Solution()
    ans = result.insertionSortList(root)
    print("After:",end='')
    ans.printList() #After:[1, 2, 3, 4]

## Python_Sol2:
* 逐一檢查每個node是否在正確位置
* 小->大
* 當前node.val<=node.next.val
* 若不合格: **針對node.next**決定其插入位置
* **從頭找**合適的位置插入

class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        
        dummy=ListNode(float('-inf'))
        dummy.next=head
        
        while head.next:
            #若安全是小->大
            if head.val<=head.next.val:
                head=head.next
            else:
                pre=dummy
                cur=head.next
                #從頭找合適的位置
                while pre.next and cur.val>pre.next.val:
                    pre=pre.next
                #連至合適的位置
                head.next=head.next.next
                cur.next=pre.next
                pre.next=cur
        return dummy.next

## C++:

#include<iostream>
#include<vector>
using namespace std;

struct ListNode{
    int val;
    ListNode *next;
    ListNode(): val(0), next(nullptr) {}
    ListNode(int x): val(x), next(nullptr) {}
    ListNode(int x, ListNode *next): val(x), next(next) {}
};

void InsertNode(ListNode *head, int data){
    ListNode *tail=head;
    if (tail->next==nullptr){
        ListNode *new_node= new ListNode(data);
        tail->next=new_node;
    }
    else
        InsertNode(tail->next,data);
}

void PrintList(ListNode *head){
    vector<int> res;
    ListNode *tail=head;
    while (tail!=nullptr){
        res.push_back(tail->val);
        tail=tail->next;
    }
    for (int i=0; i<res.size(); i++){
        cout<<res[i]<<" ";
    }
    cout<<endl;
}

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

int main(){
    ListNode *head=new ListNode(4);
    InsertNode(head,2);
    InsertNode(head,1);
    InsertNode(head,3);
    cout<<"Original List: ";
    PrintList(head); //Original List: 4 2 1 3

    Solution res;
    ListNode *ans=res.insertionSortList(head);
    cout<<"After Sorted : ";
    PrintList(ans); //After Sorted : 1 2 3 4

    return 0;
}