# Insertion Sort List

## Question

### Problem Statement

Sort a linked list using insertion sort.

A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list.
With each iteration one element (red) is removed from the input data and inserted in-place into the sorted list

Algorithm of Insertion Sort:

1. Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
2. 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.
3. It repeats until no input elements remain.

Example 1:

**Input:** 4->2->1->3
**Output:** 1->2->3->4

Example 2:

**Input:** -1->5->3->4->0
**Output:** -1->0->3->4->5

## 题解1 - 从首到尾遍历

### Python

"""
Definition of ListNode
class ListNode(object):

def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
"""
dummy = ListNode(0)
while cur is not None:
pre = dummy
while pre.next is not None and pre.next.val < cur.val:
pre = pre.next
temp = cur.next
cur.next = pre.next
pre.next = cur
cur = temp
return dummy.next

### C++

/**
* Definition of ListNode
* class ListNode {
* public:
*     int val;
*     ListNode *next;
*     ListNode(int val) {
*         this->val = val;
*         this->next = NULL;
*     }
* }
*/
class Solution {
public:
/**
*/
ListNode *dummy = new ListNode(0);
while (cur != NULL) {
ListNode *pre = dummy;
while (pre->next != NULL && pre->next->val < cur->val) {
pre = pre->next;
}
ListNode *temp = cur->next;
cur->next = pre->next;
pre->next = cur;
cur = temp;
}

return dummy->next;
}
};

### Java

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
ListNode dummy = new ListNode(0);
while (cur != null) {
ListNode pre = dummy;
while (pre.next != null && pre.next.val < cur.val) {
pre = pre.next;
}
ListNode temp = cur.next;
cur.next = pre.next;
pre.next = cur;
cur = temp;
}

return dummy.next;
}
}

### 源码分析

1. 新建 dummy 节点，用以处理最终返回结果中头节点不定的情况。
2. cur表示当前正在处理的节点，在从 dummy 开始遍历前保存cur的下一个节点作为下一轮的cur.
3. pre作为遍历节点，直到找到不小于cur值的节点为止。
4. pre的下一个节点pre->next链接到cur->next上，cur链接到pre->next, 最后将cur指向下一个节点。
5. 返回dummy->next最为最终头节点。

Python 的实现在 lintcode 上会提示 TLE, leetcode 上勉强通过，这里需要注意的是采用if A is not None:的效率要比if A:高，不然 leetcode 上也过不了。具体原因可参考 Stack Overflow 上的讨论。

## 题解2 - 优化有序链表

### Python

"""
Definition of ListNode
class ListNode(object):

def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
"""
dummy = ListNode(0)
while cur is not None:
if cur.next is not None and cur.next.val < cur.val:
# find insert position for smaller(cur->next)
pre = dummy
while pre.next is not None and pre.next.val < cur.next.val:
pre = pre.next
# insert cur->next after pre
temp = pre.next
pre.next = cur.next
cur.next = cur.next.next
pre.next.next = temp
else:
cur = cur.next
return dummy.next

### C++

/**
* Definition of ListNode
* class ListNode {
* public:
*     int val;
*     ListNode *next;
*     ListNode(int val) {
*         this->val = val;
*         this->next = NULL;
*     }
* }
*/
class Solution {
public:
/**
*/
ListNode *dummy = new ListNode(0);
while (cur != NULL) {
if (cur->next != NULL && cur->next->val < cur->val) {
ListNode *pre = dummy;
// find insert position for smaller(cur->next)
while (pre->next != NULL && pre->next->val <= cur->next->val) {
pre = pre->next;
}
// insert cur->next after pre
ListNode *temp = pre->next;
pre->next = cur->next;
cur->next = cur->next->next;
pre->next->next = temp;
} else {
cur = cur->next;
}
}

return dummy->next;
}
};

### Java

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
ListNode dummy = new ListNode(0);
while (cur != null) {
if (cur.next != null && cur.next.val < cur.val) {
// find insert position for smaller(cur->next)
ListNode pre = dummy;
while (pre.next != null && pre.next.val < cur.next.val) {
pre = pre.next;
}
// insert cur->next after pre
ListNode temp = pre.next;
pre.next = cur.next;
cur.next = cur.next.next;
pre.next.next = temp;
} else {
cur = cur.next;
}
}

return dummy.next;
}
}

### 源码分析

2. 分情况讨论，仅需要处理逆序部分。
3. 由于已经确认链表逆序，故仅需将较小值(cur->next而不是cur)的节点插入到链表的合适位置。
4. cur->next插入到pre之后，这里需要四个步骤，需要特别小心！