Sort a linked list using insertion sort.

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

插入排序。题目就是题意，将一个乱序的linked list通过插入排序的方式重新排序。

这道题不涉及算法，就是按照插入排序的思路将链表排序。当遍历链表的时候，你需要看每两个node之间是不是满足后一个node.val >= 前一个node.val，如果不满足，就需要将后一个node提出来，再从链表的头节点开始一个个遍历，最终放到合适的位置上去。其余解释请参见代码注释。

时间O(n^2)

空间O(1)

Java实现

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 class Solution {
10     public ListNode insertionSortList(ListNode head) {
11         // corner case
12         if (head == null || head.next == null) {
13             return head;
14         }
15         // normal case
16         ListNode dummy = new ListNode(0);
17         dummy.next = head;
18         // cur节点用来遍历整个list
19         ListNode cur = head;
20         ListNode temp = null;
21         ListNode prev = null;
22         // 4->2->1->3
23         while (cur != null && cur.next != null) {
24             // 如果节点顺序对，就接着往后走
25             if (cur.val <= cur.next.val) {
26                 cur = cur.next;
27             } else {
28                 // temp保存那个较小的节点值
29                 // 比如例子中一开始的2
30                 temp = cur.next;
31                 // 4 -> 1
32                 cur.next = temp.next;
33                 // prev又从头开始遍历链表
34                 prev = dummy;
35                 while (prev.next.val <= temp.val) {
36                     prev = prev.next;
37                 }
38                 // 2 -> 4
39                 temp.next = prev.next;
40                 // dummy -> 2
41                 prev.next = temp;
42             }
43         }
44         return dummy.next;
45     }
46 }

 

LeetCode 题目总结