检查链表是否为回文（递归）

Question

我正在尝试使用下面的代码，但结果总是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一直回来的。有人可以建议如何解决这个问题。

Answer 1

这就是你的算法的样子

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)

    }
}

这只是你需要向前推进的一个指针。

如果您需要再次返回原始列表，那么您可能希望复制其他对象中的列表内容并在此方法中使用该对象

希望这可以帮助！

祝你好运！