内容简介：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.回文数
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
