forked from lizeyang18/byteDanceAlgorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathtest22.java
More file actions
70 lines (65 loc) · 1.93 KB
/
test22.java
File metadata and controls
70 lines (65 loc) · 1.93 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
package byteDance;
/**
* Created by lizeyang on 2020/5/14.
* 反转链表
*/
public class test22 {
//原地反转链表,O(n)
public static ListNode reverseList(ListNode root) {
if (root == null || root.next == null) {
return root;
}
ListNode pre = null;
ListNode index = root;
ListNode last = index.next;
while (last != null) {
index.next = pre;
pre = index;
index = last;
last = last.next;
}
index.next = pre;
return index;
}
//升级->每k个反转一下,O(n)
public static ListNode reverseListK(ListNode root, int k) {
if (root == null || root.next == null) {
return root;
}
ListNode dummy = new ListNode(0), pre = dummy, cur = root, last;
dummy.next = root;
int length = 0;
while (root != null) {
length++;
root = root.next;
}
for (int i = 0; i < length / k; i++) {
for (int j = 0; j < k - 1; j++) {
last = cur.next;
cur.next = last.next;
last.next = pre.next;
pre.next = last;
}
pre = cur;
cur = pre.next;
}
return dummy.next;
}
public static void main(String[] args) {
ListNode root = new ListNode(1);
root.next = new ListNode(2);
root.next.next = new ListNode(4);
root.next.next.next = new ListNode(5);
root.next.next.next.next = new ListNode(6);
root.next.next.next.next.next = new ListNode(8);
root.next.next.next.next.next.next = new ListNode(9);
//反转链表
// ListNode res = reverseList(root);
//每k个反转链表
ListNode res = reverseListK(root, 3);
while (res != null) {
System.out.print(res.val + " ");
res = res.next;
}
}
}