# LeetCode: 147. Insertion Sort List

## 题目¶

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
```

## 解法¶

### 生成一个有序数组，然后再生成结果链表¶

```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
nodes = []

dummy = ListNode()
tail = dummy
for node in nodes:
tail.next = node
tail = node
# 防止节点上原有的 next 属性值导致出现循环
tail.next = None

return dummy.next

def insert_node(self, nodes, node):
for i, v in enumerate(nodes):
if node.val < v.val:
nodes.insert(i, node)
break
else:
nodes.append(node)

return nodes
```

### 不生成中间数组，直接对链表进行排序操作¶

• 定义一个空链表 dummy ，作为排序后的结果链表，类似上面的中间数组
• 遍历输入的链表，将节点插入到上面的 dummy 链表中，为了保持 dummy 有序，需要按上面类似 insert_node 的方法在 dummy 中找到合适的位置，因为 dummy 是个链表而不是数组无法直接插入，需要记录插入位置的上一个节点 (pre_node) 和下一个节点(next_node)，然后再基于这两个节点的信息实现插入新节点的功能。

```# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
# 新的链表
dummy = ListNode()

while current is not None:
# 把 current 插入到 dummy 链表中
# 新节点插入位置的上一个节点
pre_node = dummy
# 新节点插入位置的下一个节点
next_node = pre_node.next
while next_node is not None:
# 找到插入位置
if current.val < next_node.val:
break
pre_node = next_node
next_node = next_node.next
# 插入新节点
pre_node.next = current
_next = current.next
current.next = next_node
current = _next

return dummy.next
```