檢查一個鏈表是否是迴文（遞歸地）

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) 

    } 
} 

這只是你需要把它前進的指針。

如果你需要的所有原始列表回來了，那麼你可能要到列表內容在其他對象複製並使用該對象在這個方法中

希望這有助於！

祝你好運！

Answer 2

我誠實地不遵循您的方法的一般邏輯。我想建議一個完全不同的，有一些額外的假設。

問題列表是雙向鏈接的嗎？如果是這樣，那麼你可以從兩端穿過它，在假想回文的兩端從外部工作。如果兩端不匹配，那麼列表顯然不是迴文。

Answer 3

您應該使用Java實用程序類（或至少實現接口），並且明確地爲api添加書籤。如果你有一個雙重鏈接列表，尋找一個pallindrome是最快的，這個Java稱爲Deque。不幸的是，這種方法破壞了原文。

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丁。

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)); 
} 

Answer 4

我可以去你的方法。 你想要link.getNext()應該對之前的呼叫有影響。 你可以做到。只需更改函數原型。

public boolean isPallindrome（Link &link，Link right）;

確保您的初始呼叫不受影響。

Answer 5

問題出在：
link = link.getNext（）; 您的意圖是在所有遞歸後向調用中進行更改，但您最終所做的只是在當前堆棧中本地更改引用，並且在後續調用中未反映左側鏈接。

如果它是C，C++，你可能有鏈接左邊的鏈接**，鏈接*右邊 ，但是需要將左邊鏈接設置爲靜態外部鏈接。

Answer 6

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; 
    } 
} 

Answer 7

問題出現在左指針運動中。您將需要在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; 
    } 
} 

Answer 8

幾乎不斷縮小列表。 在下面的代碼中，第一個呼叫將保持爲第一個，最後一個爲空。 在隨後的調用中，第一個將變爲first.next，最後一個將變爲最後一個，但是列表中的一個節點的地址字段值。

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); 
}