我正在尝试下面的代码，但结果始终是true;
public boolean isPallindrome(Link link, Link right) {
if (right == null)
return true;
if (!isPallindrome(link, right.getNext())) {
return false;
}
boolean isP1 = right.getData() == link.getData();
link = link.getNext();
return isP1;
}
呼叫:-
System.out.println(link1.isPallindrome(link1.getFirst(), link1.getFirst()));
我认为罪魁祸首是right与null核对的返回。它可能总是返回true。谁能建议如何解决这个问题?
这就是你的算法的样子
boolean flag=true;
public boolean checkPalindrome(List nodeList,boolean flag)
{
if(flag==false)
return false;
if(nodeList.right==null)
return flag;
else{
Node n;//reference for travelling till last node
//traverse till last node
//check first and last node
if(same){
//delete both nodes;
}
else{
flag=false;
}
return checkPalindrome(nodeList,flag)
}
}
这只是一个指针，你需要把它向前移动
如果你需要原始列表，那么你可能需要复制列表内容到其他对象中，并在此方法中使用该对象
希望这对你有帮助!
祝你好运!
我可以按照你的方法去做。您希望link.getNext()应该对它之前的调用有影响。你能做到的。只需更改函数原型。
public boolean isPallindrome(Link &link, Link right);
确保你的初次通话没有受到影响。
问题出在:
link = link. getnext ();这里你的意图是使更改反映在所有递归向后调用中，但你最终做的是仅在当前堆栈中局部更改引用，发布左链接不反映在后续调用中。
如果是C, c++，你可以将参数设置为Link** left, Link* right但是对于引用，你需要将左链接设置为静态的
老实说，我不明白你的方法的一般逻辑。我想提出一个完全不同的建议，加上一些额外的假设。
所讨论的列表是双链接的吗?如果是这样，那么你可以从两端遍历它，从外面到假设的回文的任何一端。如果结尾不匹配，那么列表显然不是回文。
您应该使用Java实用程序类(或者至少实现接口)，并且一定要为api添加书签。如果您有一个双重链表(Java称之为Deque)，那么查找pallindrom是最快的。不幸的是，这个方法破坏了原来的。
public static boolean <E> isPallindrome(Deque<E> deque) {
if ( deque.size() <= 1 ) {
return true;
}
E first = deque.removeFirst();
E last = deque.removeLast();
if ( deque.size() == 0 ) {
return first.equals(last);
}
return isPallindrome(deque)
}
如果你想变得更花哨，你可以使用迭代器，并跳过递归。
如果您只有一个链表，那么您将需要一种到达列表末尾的方法。一种方法是跟踪列表的大小。这最终是O(n^2)，因为所有的get ting。
public static boolean isPallindrome(List<?> list, int size) {
if ( size <= 1 ) {
return true;
}
if ( ! list.get(0).equals(list.get(size-1)) ) {
return false;
}
return isPallindrome(list.subList(1,size-1));
}
问题是你的左指针移动。您需要在Java(总是按值传递)中使用左指针上的一些容器来刺激双指针(或称为引用传递)。让我们使用大小为1的数组作为容器，它将工作。我在这里用了不同的名字。
public class LinkedListS<T> {
protected Node head;
public boolean isPalindrome()
{
Node storeHead = head;
boolean result = isPalindromeUtil(new Node[]{head},head); //have to stimulate pass by reference
head = storeHead;
return result;
}
private boolean isPalindromeUtil(Node[] left,Node right)
{
if(right==null)
return true;
boolean subResult = isPalindromeUtil(left,right.next);
if (subResult==false)
return false;
boolean dataCompareResultForCurrentPosition = false;
if(left[0].data == right.data)
dataCompareResultForCurrentPosition = true;
left[0]=left[0].next; //critical
return dataCompareResultForCurrentPosition;
}
}
public class PalindromeList {
static Node left;
public static void main(String[] args) {
Node node = new Node(5);
Node node1 = new Node(4, node);
Node node2 = new Node(7, node1);
Node node4 = new Node(6, node2);
Node node5 = new Node(5, node4);
left = node5;
System.out.println(isPalindrome(node));
}
static boolean isPalindrome(Node right) {
if (right == null)
return true;
boolean isp = isPalindrome(right.next);
if (isp == false)
return false;
boolean isp1 = (right.value == left.value);
left = left.next;
return isp1;
}
}
实际上一直在缩小列表。在下面的代码中，第一次调用将保持head为first, null为last。在随后的呼叫中，first将成为first。Next和last将成为列表中倒数第一个节点地址字段的值。
boolean palindromeCheck(List first, List last)
{
//For even size of List
if(first == last)
return true;
//For odd size of List.
if(first.next == last)
return true;
List newLast = first.next;
//Traverse till last element.
while(newLast.next != last)
newLast = newLast.next;
//If value is not same, return false.
if(first.val != newLast.val)
return false;
return palindromCheck( first.next, newLast );
}