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迴文遞歸解決方案

回答

相關問題