判断一个链表是否是回文结构

题目

给定一个链表的头节点 head,请判断该链表是否为回文结构。

例如

1->2->1, 返回 true。
1->2->2->1, 返回 true。
15->6->15, 返回 true。
1->2->3, 返回 false。

进阶要求

如果链表长度为 N,时间复杂度要求达到 O(N),额外空间复杂度达到 O(1)。

解答

方法一

利用栈来判断,将所有节点压入栈中,然后弹出时就是按照逆序来弹出的,在弹出的同时与正序的原来的链表的相应的元素作比较,这样就很容易判断出是否是回文结构了。

1
2
3
4
5
6
7
8
public class Node {
public int value;
public Node next;

public Node(int value) {
this.value = value;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean isPalindrome1(Node head) {
Stack<Node> stack = new Stack<>();
Node cur = head;
// 将所有节点入栈
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
// 将栈中元素一个个弹出与原链表中的每一个元素作比较
while (head != null) {
if (head.value != stack.pop().value) { // pop 是移除并返回栈顶元素
return false;
}
head = head.next;
}
return true;
}

方法一的时间复杂度为 \(O(N)\),额外空间复杂度为 \(O(N)\)

方法二

这个方法本质上和方法一没有区别,只是,这个压栈操作有些变化,方法一是将所有的元素全部压入一个栈中,而这个方法则是先将栈给对半切割了,然后只是将右半部分的元素给压栈,然后再弹出和原链表的左半部分元素进行比较。

代码

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
public boolean isPalindrome2(Node head) {
if (head == null || head.next == null) {
return true;
}
Node right = head.next;
Node cur = head;
// 利用快慢指针,快速将 right 移动到链表中点的位置
// 设链表节点数为 N,
// 则当 N 为偶数时,cur 指针最终走到 N - 1 处,right 走了 (N - 2) / 2 步,最终走到 N / 2 的下一个位置
// 当 N 为奇数时,cur 指针最终走到 N 处,right 走了 (N - 1) / 2 步,最终走到 (N + 1) / 2 这个位置,即正好是正中间的位置
while (cur.next != null && cur.next.next != null) {
right = right.next;
cur = cur.next.next;
}
// 把右半部分的节点给压入堆栈
Stack<Node> stack = new Stack<>();
while (right != null) {
stack.push(right);
right = right.next;
}
while (!stack.isEmpty()) {
if (head.value != stack.pop().value) {
return false;
}
head = head.next;
}
return true;
}

方法二的时间复杂度为 \(O(N\),额外空间复杂度为 \(O(N)\)

方法三

方法三的主要思想是将链表从中间截断,然后使中间节点指向 null,然后逆转右半部分的链表,然后左边和右边分别并同时从最左边的和最右边的节点进行遍历,比较它们每一个节点是否相同。最后,要将逆转的链表恢复原状。

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
public boolean isPalindrome3(Node head) {
if (head == null || head.next == null) {
return true;
}
Node n1 = head;
Node n2 = head;
// N 为偶数,n1 走到 N / 2 位置
// N 为奇数,n1 走到 N / 2 位置
while (n2.next != null && n2.next.next != null) { // 利用快慢指针查找中间节点
n1 = n1.next; // n1 -> 中部
n2 = n2.next.next; // n2 -> 尾部
}
n2 = n1.next; // n2 -> 右部分第一个节点
n1.next = null; // mid.next -> null
Node n3 = null;
while (n2 != null) { // 右半区反转
n3 = n2.next; // n3 -> 保存下一个节点
n2.next = n1;
n1 = n2; // n1 移动
n2 = n3; // n2 移动
}
n3 = n1; // n3 -> 保存最后一个节点
n2 = head; // n2 -> 左边第一个节点
boolean res = true;
while (n1 != null && n2 != null) { // 反转之后的检查回文
if (n1.value != n2.value) {
res = false; // 因为之后要恢复被反转的链表,所以要先将结果存储起来,不能直接返回
break;
}
n1 = n1.next; // 从左到中部
n2 = n2.next; // 从右到中部
}
n1 = n3.next; // 这里的 n3 是原来链表的最后一个节点,n3.next 即倒数第二个节点
n3.next = null;
while (n1 != null) { // 恢复链表
n2 = n1.next; // 保存下一个节点
n1.next = n3; // 反转
n3 = n1; // 移动 n3
n1 = n2; // 移动 n1
}
return res;
}