题目描述
给定单向链表 LO-L1-L2… … -L(N-1)-LN
重排序后的链表为：LO-LN-L1-L(N-1)-L2-L(N-2)… …
要求时间复杂度O(n)，且只能改变next指针，不能增加额外的节点
思路
遍历一遍，找到链表长度后，求出中间节点的index，同时用引用tail指向尾节点
再从头节点开始找到中间节点，从中间节点开始将链表反转
最后不断改变head和tail的next，以及head和tail的引用，即可完成链表的重排序
代码
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
| public class Main {
static class Node {
public Node next;
public int num;
public Node(int num) {
this.num = num;
}
}
public static void main(String[] args){
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
Node n6 = new Node(6);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n6;
new Main().reverse(n1);
while(n1 != null) {
System.out.println(n1.num);
n1 = n1.next;
}
}
public void reverse(Node head) {
// 获取链表长度
int length = 0;
Node header = head;
while(header.next != null) {
length++;
header = header.next;
}
Node tail = header;
// 以中间节点作为头节点，反转链表
int mid = (length+1)/2;
int count = 0;
Node start = head;
while(count < mid) {
count++;
start = start.next;
}
// 从mid节点开始将链表反转
Node cur = start.next;
Node pre = start;
while(cur != null) {
Node tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
// 重排链表
while(head != tail && head.next != tail) {
Node nextHead = head.next;
Node nextTail = tail.next;
head.next = tail;
tail.next = nextHead;
head = nextHead;
tail = nextTail;
}
if(head == tail) {
tail.next = null;
}else {
head.next = tail;
tail.next = null;
}
}
}
|
考差点