public boolean palindromLinkedList() {
//find size
Node temp = head;
int size=0;
while(temp != null){
size++;
temp=temp.next;
}
//find while loop iteration
int c;
if(size%2 ==0){
c = size/2;
}else{
c = (size+1)/2;
}
//intialise start and end pointer
Node start = head;
Node end = tail;
//index pointer
int k =size-1;
//loop for the palindrome condition
while(c > 0)`
if(start.data != end.data){
return false;
}
start = start.next;
Node find = head;
k--;
for(int i=0;i<=k;i++){
find = find.next;
}
end = find;
c--;
}
return true;
}
我尝试使用类似于两个指针的方法来检查链表是否是回文。
我初始化了两个变量:start = head
和end = tail
。
Start从start开始检查节点,end从tail开始检查,在检查start和end值的数据是否相等后,我将更改后的起始点设置为下一个节点,并使用for循环查找end的前一个节点,并继续此过程,直到指针到达中间节点。
如果链表是回文,则返回true或false。我认为我的方法是正确的,但似乎有什么我错过了。
3条答案
按热度按时间du7egjpx1#
看起来你实现了自己的链表,这使得这个问题很难回答。
但是,假设您的代码类似于java.util.LinkedList:
java中的
==
检查引用,而不是给定的Object。您应该使用.equals
来比较节点数据。更好的是Objects.equals(start.data, end.data)
,因为它也可以处理null
。这种行为的一个很好的例子是字符串。Java收集你在程序中硬编码的字符串,所以它有时能工作,但大多数时候不能。
我建议你实现一个双向链表,因为它会提高性能,在这种情况下,让你的生活更容易。它基本上也添加了对前一个节点的引用。因此,您不需要循环遍历所有元素,而是可以使用
end.previous
获取前一个节点。krcsximq2#
问题出在这行代码中:
此循环将一次迭代转化为多次迭代。更改为:
这将解决即使是最简单的测试用例也会得到错误的输出。
但现在你会遇到另一个问题:这个代码太慢了。为了确定 * 在 *
end
之前的节点而必须执行的重复循环代价太高,并且使您的实现具有O(𝑛²)的时间复杂度。你得想个更好的主意。这个问题以前已经解决过很多次了,而且在这个网站上,你会找到更有效的方法来解决这个问题的解释。
yacmzcpb3#
旁注:
你应该将“size”变量作为链表实现的一部分来存储,而不是用循环来计算它。你知道什么时候有东西被添加到你的链表中;大小加1。你知道什么时候有东西从你的链表中删除了;尺寸减1。
主要React:
如果不使用外部结构(如Stack),或者将链表转换为双向链表,您将不得不反复使用循环来找出“结束”位置的节点。
但是,您可以通过从“开始”位置开始并向前跳转所需的次数来减少迭代次数。
在第一次比较时,“结束”位置将是
size - 1
跳离“开始”。之后,每次跳跃的次数减少2次,因为“开始”向前移动了1次,“结束”向后移动了1次。考虑到这一点,您可以简单地保持比较,只要
(required number of jumps to get from "start" to "end" >= 1
。它看起来像这样: