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

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

Github 同步地址：

https://github.com/grandyang/leetcode/issues/147

Sort List

Insert into a Cyclic Sorted List

https://leetcode.com/problems/insertion-sort-list/

https://leetcode.com/problems/insertion-sort-list/discuss/46423/Explained-C%2B%2B-solution-(24ms)

https://leetcode.com/problems/insertion-sort-list/discuss/46420/An-easy-and-clear-way-to-sort-(-O(1)-space-)

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation