forked from crossoverJie/JCSprout
-
Notifications
You must be signed in to change notification settings - Fork 0
/
LinkedListMergeSort.java
141 lines (118 loc) · 3.86 KB
/
LinkedListMergeSort.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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
package com.crossoverjie.algorithm;
/**
* 链表排序, 建议使用归并排序,
* 问题描述,给定一个Int的链表,要求在时间最优的情况下完成链表元素由大到小的排序,
* e.g: 1->5->4->3->2
* 排序后结果 5->4->3->2->1
*
* @author [email protected]
* @date 6/7/2018 11:42 PM
* @since 1.0
*/
public class LinkedListMergeSort {
/**
* 定义链表数据结构,包含当前元素,以及当前元素的后续元素指针
*/
final static class Node {
int e;
Node next;
public Node() {
}
public Node(int e, Node next) {
this.e = e;
this.next = next;
}
}
public Node mergeSort(Node first, int length) {
if (length == 1) {
return first;
} else {
Node middle = new Node();
Node tmp = first;
/**
* 后期会对这里进行优化,通过一次遍历算出长度和中间元素
*/
for (int i = 0; i < length; i++) {
if (i == length / 2) {
break;
}
middle = tmp;
tmp = tmp.next;
}
/**
* 这里是链表归并时要注意的细节
* 在链表进行归并排序过程中,会涉及到将一个链表打散为两个独立的链表,所以需要在中间元素的位置将其后续指针指为null;
*/
Node right = middle.next;
middle.next = null;
Node leftStart = mergeSort(first, length / 2);
Node rightStart;
if (length % 2 == 0) {
rightStart = mergeSort(right, length / 2);
} else {
rightStart = mergeSort(right, length / 2 + 1);
}
return mergeList(leftStart, rightStart);
}
}
/**
* 合并链表,具体的实现细节可参考<code>MergeTwoSortedLists</code>
*
* @param left
* @param right
* @return
*/
public Node mergeList(Node left, Node right) {
Node head = new Node();
Node result = head;
/**
* 思想就是两个链表同时遍历,将更的元素插入结果中,同时更更大的元素所属的链表的指针向下移动
*/
while (!(null == left && null == right)) {
Node tmp;
if (left == null) {
result.next = right;
break;
} else if (right == null) {
result.next = left;
break;
} else if (left.e >= right.e) {
tmp = left;
result.next = left;
result = tmp;
left = left.next;
} else {
tmp = right;
result.next = right;
result = tmp;
right = right.next;
}
}
return head.next;
}
public static void main(String[] args) {
Node head = new Node();
head.next = new Node(7,
new Node(2,
new Node(5,
new Node(4,
new Node(3,
new Node(6,
new Node(11, null)
)
)
)
)
)
);
int length = 0;
for (Node e = head.next; null != e; e = e.next) {
length++;
}
LinkedListMergeSort sort = new LinkedListMergeSort();
head.next = sort.mergeSort(head.next, length);
for (Node n = head.next; n != null; n = n.next) {
System.out.println(n.e);
}
}
}