【算法】判断一个链表是否为回文结构
题目
给定一个链表的头节点head，请判断该链表是否为回 文结构。 例如: 1->2->1，返回true。 1->2->2->1，返回true。 15->6->15，返回true。 1->2->3，返回false。 进阶： 如果链表长度为N，时间复杂度达到O(N)，额外空间复杂 度达到O(1)。
链表结构如下
public static class Node {
public Node next;
public int value;
public Node(int data) {
value = data;
}
}1、基础版--空间复杂度O(N)
思路：
使用栈，将链表的所有数据入栈。然后链表从头开始遍历，每次指针指向下一个节点时，栈弹出，判断两者是否相等，直至栈空都相等的话，那么就是回文链表。
代码实现
public static boolean isPalindromeList1(Node head) {
Stack<Node> stack = new Stack<Node>();
Node p = head;
while(p != null) {
stack.push(p);
p = p.next;
}
while(head != null) {
Node node = stack.pop();
if (node.value != head.value) {
return false;
}
head = head.next;
}
return true;
}2、进阶版1--空间复杂度O(N/2)
思路
回顾上面的解法，其实我们只需比较到链表的中点即可。因此，我们不再对链表全部入栈，而是先找到链表的中点，然后从中点开始入栈。最后只需比较链表~中点之间的数据和链表是否一一相等即可
算法实现
public static boolean isPalindromeList2(Node head) {
Node right = head.next;
Node cur = head.next.next;
// 找到中点节点
while(cur.next != null && cur.next.next != null) {
right = right.next;
cur = cur.next.next;
}
// 从中间回文开始的节点入栈
Stack<Node> stack = new Stack<Node>();
while(right != null) {
System.out.println(right.value);
stack.push(right);
right = right.next;
}
// 比较前回文和后回文部分
while(!stack.isEmpty()) {
Node node = stack.pop();
if (node.value != head.value) {
return false;
}
head = head.next;
}
return true;
}这里需要提到中点链表的查找方法： 1、准备一个慢指针，一次走1格 2、准备一个快指针，一次走2格 3、当快指针走完了，那么慢指针所指向的节点就是中点节点。若不理解，自己画图理解理解
3、进阶版2--空间复杂度O(1)
思路
修改链表的指向，将回文部分链表逆转指向中点，例如： 1 -> 2 -> 3 -> 2 -> 1改为 1 -> 2 -> 3 <- 2 <- 1 这种结构判断 因此，算法步骤如下： 1、我们需要先找到中点节点，然后修改尾节点~中点节点的指向，翻转节点 2、首尾指针开始遍历链表，直至首尾的指针抵达中点，期间判断首尾指针指向的value是否相等 3、还原链表原来的结构（如果要求不能修改链表结构的话，就需要做这步骤，算是可选步骤吧）
算法实现
public static boolean isPalindromeList3(Node head) {
Node right = head.next;
Node cur = head.next.next;
// 找到中间节点
while(cur.next != null && cur.next.next != null) {
right = right.next;
cur = cur.next.next;
}
// 右边第一个节点
Node n1 = right.next;
// 使中间节点指向null
right.next = null;
Node pre = null;
Node next = null;
// 以中间开始，翻转节点
while(n1 != null) {
next = n1.next;
n1.next = pre;
pre = n1;
n1 = next;
}
// 右边部分的head节点
Node rightHead = pre;
Node leftHead = head;
// 备份最后的指针
Node lastNode = pre;
boolean res = true;
while(leftHead != null && rightHead != null) {
if(leftHead.value != rightHead.value) {
res = false;
break;
}
leftHead = leftHead.next;
rightHead = rightHead.next;
}
// 恢复原来的链表结构，可选步骤
n1 = lastNode;
pre = null;
next = null;
while(n1 != null) {
next = n1.next;
n1.next = pre;
pre = n1;
n1 = next;
}
// 将中间节点重新指向翻转后的最后节点
right.next = pre;
return res;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录