如何高效的检测单链表是否是回文链表呢
-
方法一
遍历一遍 计数 然后再找到中间node 开始对比 -
方法二
进步指针f、s后者是前者两倍 到null截至
同时栈入f 判断s是否null 来决定和栈出对比的起点

代码
package _09_Linear.list;
import java.util.Stack;
/**
* 回文链表 检测回文
*/
public class PalindromeLinkedList {
static class Node {
Object value;
Node next;
Node(Object value) {
this.value = value;
}
}
public static void main(String[] args) {
int arr[] = {1, 2, 3, 4, 4, 3, 2, 1};
int arr1[] = {1, 2, 3, 4, 5, 3, 2, 1};
int arr2[] = {1, 2, 3, 4, 3, 2, 1};
Node head = new Node(null);
Node p = head;
for (int i : arr) {
p.next = new Node(i);
p = p.next;
}
System.out.println(checkPalindrome(head));
}
private static boolean checkPalindrome(Node head) {
Node f = head.next;
Node s = head.next;
Stack<Node> stack = new Stack<>();
while (s != null && s.next != null) {
stack.push(f);//入栈
f = f.next;
s = s.next.next;
}
if (s != null) {//奇数个//1 2 3 4(f) 1 2 3 4(s) s==null 就是 奇数个
f = f.next;//后移
}
System.out.println("第二个指针的位置:" + f.value);
while (!stack.empty()) {
if (stack.pop().value == f.value) {//出栈
f = f.next;
} else {
return false;
}
}
return true;
}
}
本文作者:Author: 寒光博客
文章标题:[java] 回文链表检测
本文地址:https://dxoca.cn/java/300.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
本文地址:https://dxoca.cn/java/300.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。