/
_147.java
executable file
·46 lines (44 loc) · 1.42 KB
/
_147.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
package com.hit.basmath.learn.others;
import com.hit.common.ListNode;
/**
* 147. Insertion Sort List
* <p>
* Sort a linked list using insertion sort.
* <p>
* 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
* <p>
* Algorithm of Insertion Sort:
* <p>
* 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.
* <p>
* Example 1:
* <p>
* Input: 4->2->1->3
* Output: 1->2->3->4
* <p>
* Example 2:
* <p>
* Input: -1->5->3->4->0
* Output: -1->0->3->4->5
*/
public class _147 {
public ListNode insertionSortList(ListNode head) {
ListNode helper = new ListNode(0);
ListNode pre = helper;
ListNode current = head;
while (current != null) {
pre = helper;
while (pre.next != null && pre.next.val < current.val) {
pre = pre.next;
}
ListNode next = current.next;
current.next = pre.next;
pre.next = current;
current = next;
}
return helper.next;
}
}