-
Notifications
You must be signed in to change notification settings - Fork 6
Expand file tree
/
Copy pathSortList.java
More file actions
125 lines (107 loc) · 2.61 KB
/
Copy pathSortList.java
File metadata and controls
125 lines (107 loc) · 2.61 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
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
package leetcode;
import java.util.List;
public class SortList {
public static void main(String[] args) {
}
static ListNode sortlist(ListNode head) {
if (head==null || head.next==null)
return head;
ListNode mid = head;
ListNode step2 = head.next;
while (mid != null && step2 != null) {
mid = mid.next;
step2 = step2.next.next;
}
ListNode left = sortlist(mid.next);
mid.next = null; //
ListNode right = sortlist(head);
return merge(left, right);
}
static ListNode merge(ListNode left, ListNode right) {
if (left == null)
return right;
else if (right == null)
return left;
ListNode tmp = null;
if (left.val < right.val) {
tmp = left;
left = left.next;
} else {
tmp = right;
right = right.next;
}
tmp = tmp.next;
while (left != null && right != null) {
if (left.val < right.val) {
tmp.next = left;
left = left.next;
} else {
tmp.next = right;
right = right.next;
}
tmp = tmp.next;
}
if (left!=null)
tmp.next = left;
if (right!=null)
tmp.next = right;
return tmp;
}
}
/**
* Definition for singly-linked list.
*/
class ListNode {
public int val;
public ListNode next = null;
public ListNode(int val) {
this.val = val;
}
public ListNode(int va[]) {
if (va == null)
return;
val = va[0];
ListNode cur = this;
for (int i = 1; i < va.length; i++) {
ListNode node = new ListNode(va[i]);
cur.next = node;
cur = cur.next;
}
}
public void append(ListNode node) {
next = node;
}
public void show() {
ListNode tmp = this;
while (tmp != null) {
System.out.printf("%d ", tmp.val);
tmp = tmp.next;
}
}
public ListNode reverse() {
ListNode h = this;
ListNode prev = null;
while (h != null) {
ListNode nxt = h.next;
h.next = prev;
prev = h;
h = nxt;
}
return prev;
}
}
//链接：https://www.nowcoder.com/questionTerminal/d75c232a0405427098a8d1627930bea6
// 来源：牛客网
/*
考点：
1. 快慢指针；2. 归并排序。
此题经典，需要消化吸收。
复杂度分析:
T(n) 拆分 n/2, 归并 n/2 ，一共是n/2 + n/2 = n
/ \ 以下依此类推：
T(n/2) T(n/2) 一共是 n/2*2 = n
/ \ / \
T(n/4) ........... 一共是 n/4*4 = n
一共有logn层，故复杂度是 O(nlogn)
*/