LinkedList回文递归解决方案

-1

我正在阅读一本编码书，并且难以理解解决方案以检查LinkedList是否是回文。LinkedList回文递归解决方案

提供的解决方案如下：

public class Result { 
    public LinkedListNode node; 
    public boolean result; 
} 

public Result isPalindromeRecurse(LinkedListNode head, int length) { 
    if (head == null || length == 0) { 
     return new Result(null, true); 
    } else if (length == 1) { 
     return new Result(head.next, true); 
    } else if (length == 2) { 
     return new Result(head.next.next, head.data == head.next.data); 
    } 
    Result res = isPalindromeRecurse(head.next, length - 2); 
    if (!res.result || res.node == null) { 
     return res; 
    } else { 
     res.result = head.data == res.node.data; 
     res.node = res.node.next; 
     return res; 
    } 
} 

public boolean isPalindrome(LinkedListNode head) { 
    Result p = isPalindromeRecurse(head, size); 
    return p.result; 
}

我了解整个逻辑，在经过长-2可以让我们知道一旦我们已经达到了中间的元素，以帮助形成基本情况。然而，我很难想象除了基本情况比较以外，如何进行其他节点比较更接近中间元素。如果任何人都可以向我解释这一点，并帮助我通过代码和递归，我会很感激。

来源

2015-09-04 Jay S

假设你有一个包含

A B C D E F

的算法由下面的递归规则列表：A B C D E F是回文如果B C D E是回文和A以下E等于元素。

如果递归的使用规则，你也有：B C D E是回文如果C D是回文和B以下D等于元素。

然后你在长度为2的基本情况下，其中规则是C D是回文，如果C等于D。

这就是为什么结果类包含布尔值（true或false）和节点。该节点是检查序列的最后一个节点，它允许下一步获取上一步骤的最后一个节点之后的元素。

来源

2015-09-04 20:52:59

谢谢！我理解这一逻辑，但我仍然在努力将其反映在代码中。例如，如果我们的列表如下所示：1-> 2-> 3-> 4-> 5。我们按照以下顺序递归：isPalindromeRecurse（head.next，5），res = isPalindromeRecurse（head.next，3），res = isPalindromeRecurse（head.next，1）。后者运行第一，它已经是基本情况？那么会发生什么，res res = Result（head.next，true）？那么，什么？如果有人能够帮助我逐步理解它，我只是无法通过此代码。 –

您应该使用一个调试器并逐步执行代码，随时检查变量。 –

基本上，代码将进行递归，直到它到达列表中间。然后，您需要比较从中间开始的所有索引对(i, length - i - 1)。索引i的元素由head指向，第二个索引的元素由res.node指向。

会发生什么是递归调用会将head指针推向中间，当它返回时，res.node将是head的对称元素。然后，返回一个包含node.next的新结果，并且您将在之前的递归调用中处理此结果，其中head是当前头的前身。因此，您将左边的res.node推向右边，head左边：它们仍然是对称元素。

来源

2015-09-04 21:01:58 Dici

LinkedList回文递归解决方案

回答

相关问题