内容简介：Everyone thinks of changing the world, but no one thinks of changing himself.不借助外部存储来实现判断回文，这里用到了链表反转的思想。先使用快慢指针法找到链表的后半部分，然后将其反转再进行比较
Everyone thinks of changing the world, but no one thinks of changing himself.
上海自来水来自海上，中山诸罗茶罗诸山中。非常有意境的句子，正着读倒着读都是一个意思。非常对陈，强迫症患者福音。本文分享了基于单链表判断回文的三种方法。所有源码均已上传至github： 链接
基于数组
用数组存储链表前半段的值，使用快慢指针法来进行截取。
但是这种数组的倒序插入比较费时。
小技巧 ：一直使用node.add(0,slow.data)相当于倒序插入
private boolean isPalindromeByArray(Node node) {
if (null == node || null == node.next) return true;
List<Integer> nodeList = new ArrayList<>();
Node fast = node;
Node slow = node;
nodeList.add(0, slow.data);
while (null != fast.next && null != fast.next.next) {
fast = fast.next.next;
slow = slow.next;
nodeList.add(0, slow.data);
}
Node curNode = slow;
if (null != fast.next) {
curNode = slow.next;
}
int index = 0;
while (null != curNode) {
if (curNode.data != nodeList.get(index)) {
return false;
}
curNode = curNode.next;
++index;
}
return true;
}复制代码
基于栈
和数组的思想是一样的，只不过存储方式换成了栈，然后不断地出栈和链表后半段比较即可。这种方式比较高效。
private boolean isPalindromeByStack(Node node) {
if (null == node || null == node.next) return true;
Stack<Integer> stack = new Stack<>();
Node fast = node;
Node slow = node;
stack.push(slow.data);
while (null != fast.next && null != fast.next.next) {
fast = fast.next.next;
slow = slow.next;
stack.push(slow.data);
}
if (null != fast.next) {
slow = slow.next;
}
Node curNode = slow;
while (null != curNode) {
if (curNode.data != stack.pop()) {
return false;
}
curNode = curNode.next;
}
return true;
}复制代码
原地链表法
不借助外部存储来实现判断回文，这里用到了链表反转的思想。先使用快慢指针法找到链表的后半部分，然后将其反转再进行比较
private boolean isPalindromeAuto(Node node) {
if (null == node || null == node.next) return true;
Node fast = node;
Node slow = node;
while (null != fast.next && null != fast.next.next) {
fast = fast.next.next;
slow = slow.next;
}
Node preNode = slow;
Node firstNode = slow.next;
Node curNode = slow.next.next;
firstNode.next = null;
while (null != curNode) {
Node nextNode = curNode.next;
curNode.next = preNode.next;
preNode.next = curNode;
curNode = nextNode;
}
slow = node;
fast = preNode.next;
while (null != fast) {
if (fast.data != slow.data) {
return false;
}
slow = slow.next;
fast = fast.next;
}
return true;
}复制代码
测试结果
end
您的点赞和关注是对我最大的支持，谢谢！
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
- 回文算法（JavaScript）
- 让我们一起啃算法----回文数
- 每日一道 LeetCode (3)：回文数
- java算法题：最长回文串
- 每天一道leetcode234-回文链表
- leetcode刷题（python解题）-----9.回文数
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
