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
您的点赞和关注是对我最大的支持，谢谢！
