forked from rpj911/LeetCode_algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathInsertionSortList.java
More file actions
51 lines (41 loc) · 1.39 KB
/
InsertionSortList.java
File metadata and controls
51 lines (41 loc) · 1.39 KB
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
47
48
49
50
51
package Algorithms.sort;
import Algorithms.algorithm.others.ListNode;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class InsertionSortList {
public ListNode insertionSortList(ListNode head) {
// 使用dummy node来记录新的头节点，每次把旧链找合适的位置来插入即可
if (head == null) {
return null;
}
ListNode dummy = new ListNode(0);
// 记录下插入位置的前趋节点.
ListNode pre = dummy;
while (head != null) {
// every time we should reset the pre to the BEGIN OF THE LIST.
pre = dummy;
// 这样可以找到pre.next为第一个比head大的节点
// if we use <= here we can keep the Algorithm stable.
while (pre.next != null && pre.next.val <= head.val) {
pre = pre.next;
}
// backup the next node of head;
ListNode tmp = head.next;
// Insert the head between PRE and PRE.next.
head.next = pre.next;
pre.next = head;
// set head to the next node.
head = tmp;
}
return dummy.next;
}
}