内容简介：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
您的点赞和关注是对我最大的支持，谢谢！
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
光线跟踪算法技术
萨芬 / 刘天慧 / 清华大学出版社 / 2011-3 / 98.00元
《光线跟踪算法技术》详细阐述了与光线跟踪问题相关的高效解决方案及相应的数据结构和算法，主要包括采样技术、投影视图、视见系统、景深、非线性投影、立体视觉、光照与材质、镜面反射、光泽反射、全局光照、透明度、阴影、环境遮挡、区域光照、光线与对象间的相交计算、对象变换、栅格技术以及纹理映射技术等内容。此外，《光线跟踪算法技术》还提供了相应的算法、代码以及伪代码，以帮助读者进一步理解计算方案的实现过程。 ......一起来看看 《光线跟踪算法技术》 这本书的介绍吧!
