我编写了一段代码来检查单链表是否是回文。我做了两步:
第一。反转原来的链表。
第二。检查原链表和反向链表是否有相同的元素。
public static Boolean isPalindrome(Node input){
Node reversed= reverse(input);
while (input!=null){
if(input.item!=reversed.item)
return false;
input=input.next;
reversed=reversed.next;
}
return true;
}
static Node head;
public static Node reverse(Node input){
if(input==null || input.next==null){
head=input;
return input;
}
else{
reverse(input.next);
input.next.next=input;
input.next=null;
return head;
}
}
这个程序有效。但我想,当执行reverse方法时,由于传入了原始链表的头,所以原始链表也可能发生变化,所以isPalindrome也应该返回true,对吧?我是对的还是你能告诉我我是否误解了任何概念?谢谢
这是主要功能以及我如何使用该代码:
public static void main(String [] args){
Node a=new Node(9);
Node b=new Node(8);
Node c=new Node(7);
Node d=new Node(6);
a.next=b;
b.next=c;
c.next=d;
//d.next=c;
Boolean tf=isPalindrome(a);
if (tf)
System.out.println("Is Palindrome!");
else
System.out.println("Not Palindrome");
}
其实你的方法是not在职的。尝试获取包含以下内容的列表3,4,5,3
。它会返回true
.
此外,它还更改了传递给它的列表,这不是一个好主意。如果你做类似的事情System.out.println(a)
(假设你写了一个正确的toString()
方法)运行你的方法后,你会惊讶地发现它只有一项......
这确实是因为传递对象引用就像在语言中传递指针一样C
。如果您更改该对象的内容(最终您会这样做,因为在reverse
你把null
in its next
),然后它保持改变。
那么为什么你的程序会返回true
?因为input
正如我所说,变成一个单项列表。reversed
包含完整的反向列表,并且input
仅指向其最后一项。既然你循环播放input
, then 如果第一项和最后一项相同, 你会得到true
- 列表是否是回文。那是因为您只迭代了一项input
正在指向。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)