在编写检查链表是否回文的代码时,我创建了一个reverseLL函数,该函数返回一个反向链表和一个要检查的isPallindrome函数。问题是循环内的return语句未被检测到并且只有最后一个语句返回 true;每次都被执行: 我通过将 LL 分为两部分并反转后半部分来检查 LL 是否为回文,然后比较两半
public static Node<Integer> reverseLL(Node<Integer> head){
Node<Integer> prev = null;
Node<Integer> current = head;
Node<Integer> next = null;
while(current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
return head;
}
public static boolean isPallindrome(Node<Integer> head) {
if(head == null || head.next == null) {
return true;
}
Node<Integer> fast = head;
Node<Integer> slow = head;
while(fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
Node<Integer> secondHead = slow.next;
slow.next = null;
secondHead = reverseLL(secondHead);
Node<Integer> p = secondHead;
Node<Integer> q = head;
while(p != null) {
if(p.data != q.data) {
return false;
}
p = p.next;
q = q.next;
}
return true;
}
最佳答案
我不会运行你的代码,因为它不完整。但是,看起来您找到了列表的最后一个元素并从那里反转它,而没有考虑到它也反转了 yuo 已经用 head
引用的列表。因此,当您启动比较循环时,您将有一个指向反转列表中第一个元素的指针和一个指向反转列表中最后一个元素的指针。您绝对不会将列表分成两部分。
您的代码也过于复杂。正确的算法是:
find head and tail of list
while (head != tail) {
if (head.value != tail.value)
return false;
head = head.next;
tail = tail.prev;
}
不需要两个循环变量来查找链表的尾部。正确的算法是:
tail = head
while (tail.next != null) {
tail = tail.next;
}
此外,通常不能将整数与相等运算符进行比较。您必须将它们拆箱为原始整数或使用 equals。尝试运行:
System.err.println(new Integer(1) == new Integer(1));
System.err.println(new Integer(1).equals(new Integer(1)));
关于Java,函数不识别return语句,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60057271/