檢查鏈接列表是否迴文

Question

考慮鏈接列表，其節點是字符，因此列表表示一個字符串。你怎麼寫一個遞歸例程來檢查字符串是否是一個迴文，以便 該函數在處理字符串中間的字符時開始展開堆棧？

例如，假設我的字符串是「夫人」。我的遞歸函數看起來像：

bool isPalin(const node *startnode, const node *currentnode, const node *midpoint, ...);

當currentnode->data == 'd'，堆棧有放鬆。

我被問到這個問題的採訪;目前我無法想象這個問題的任何用途，除非是一個非常困難的難題。

的第一個想法：一個很明顯的（如果不雅）的方法是：

1. 計算列表中點第一。
2. 如果currentnode在「之前」midpoint，手動推入前一個堆棧。這可以通過維護一個計數器來決定。
3. 否則，在遞歸的每個步驟中展開手動維護的堆棧，並與當前字符進行比較。

任何更好的想法或新鮮見解？

Answer 1

如果你覺得自己像使用堆棧，這是利用不確定性下推自動機在計算理論的共同演習。這個想法是推動每個字符堆棧和每個字符，分支，一個分支跳過一個字符（如果它是一個奇怪的迴文），並將每個字符從堆棧中彈出，同時將其與列表中其餘部分中的字符進行比較，另一個分支在不跳過初始字符的情況下執行相同的操作（如果它是一個偶數迴文），第三個分支繼續向堆棧中添加元素（並遞歸地開始再次使用下一個字符分支）。這三個分支可以通過遞歸地將棧的當前狀態傳遞給每個分支來表示。

僞代碼：

function isPalin(* start, * end, stack){ 
    if checkPalin(start, end, stack): 
    return true; 

    stack.push(*start); 
    if checkPalin(start, end, stack): 
    return true; 

    if (start == end) 
    return false; 

    return isPalin(start.next, end, stack); 
} 

function checkPalin(* start, * end, stack){ 
    while (stack is not empty && start != end){ 
    start = start.next; 
    if (*start != stack.pop()) 
     return false; 
    } 

    return (stack is empty && start == end); 
} 

Answer 2

首先，迭代到列表的末尾，並將指向最後一個節點的指針存儲爲end。然後將指向第一個節點的指針存儲爲start。

然後，調用一個函數並提供這些值。該功能將：

1. 測試是否start == end（它們指向相同的鏈接）。如果是這樣，它會立即返回true。 （列表中的奇數個項目和中間項目是唯一剩下的項目。）
2. 然後它會查看start和end所代表的值。如果它們不相等，它會立即返回錯誤。 （不是迴文）
3. 否則，它會改變start指向下一個鏈接（推測爲start = start->next）。
4. 如果start == end，立即返回true（處理列表中偶數個鏈接的情況）。
5. 找到之前的鏈接end並設置爲end：link i = start; while (i->next != end) i = i->next; end = i;。
6. 遞歸，提供start和end的新值。

Answer 3

通過「鏈表」，你的意思是std::list？

template <typename BiDiIterator> 
bool isPalindrome(BiDiIterator first, BiDiIterator last) { 
    if (first == last) return true; 
    --last; 
    if (first == last) return true; 
    if (*first != *last) return false; 
    return isPalindrome(++first, last); // tail recursion FTW 
} 

isPalindrome(mylist.begin(), mylist.end()); 

我已經使用了這樣的事實，即可以從頭開始迭代以及從頭開始向前迭代。這是否由問題給出尚不清楚。

使用單向鏈表可以運行兩個迭代器，一個快一個，一個慢。在每次通話中，增加兩次快速和慢一次。當快速列表到達列表末尾時，慢速列表處於中點（um，+/- 1，並考慮到奇數列和偶數列）。此時，退出比較字符值的遞歸。 （n）運行時和內存使用的複雜性（不是尾遞歸）。

我會寫代碼，但現在是在英國睡覺的時候了。

[編輯：早上，所有的

template <typename FwdIterator> 
std::pair<FwdIterator, bool> isPalindrome(FwdIterator slow, FwdIterator fast, FwdIterator last) { 
    if (fast == last) return std::make_pair(slow, true); 
    ++fast; 
    if (fast == last) return std::make_pair(++slow, true); 
    ++fast; 
    FwdIterator next = slow; 
    std::pair<FwdIterator, bool> result = isPalindrome(++next, fast, last); 
    if (result.second == false) return result; 
    if (*slow != *(result.first)) return std::make_pair(slow, false); 
    ++(result.first); 
    return result; 
} 

... 

isPalindrome(mylist.begin(), mylist.begin(), mylist.end()).second; 

如果出於某種奇怪的原因，你的鏈接列表不提供迭代器，然後希望等效代碼if (fast->next == 0)，fast = fast->next，等等，是顯而易見的。當然，你可以用一個包裝來清理用戶界面。

我認爲如果允許您臨時修改列表，則可以避免使用額外的存儲空間，方法是將列表逆轉爲下降時的「緩慢」，然後在您上升時再次反轉。這樣，您就不需要在遞歸調用中存儲slow的副本：相反，您可以返回一個額外的指針供調用者使用。不過，我不打擾。

]

Answer 4

該列表是否雙向鏈接？然後就是傳遞開始和結束節點，比較它們指向的內容。如果它們不同，請返回false。如果它們相同，則用start + 1和end-1遞歸地調用自己，直到start> end。

Answer 5

Modulo棘手的細節這個很容易。

首先，通過調用遞歸移動一個指針而不是其他兩個步驟來找到中點。當兩步指針到達結束時，一步指針位於中間。棘手的事情：甚至與奇數長度的名單。

然後備份（從遞歸調用返回），同時支持每次返回向前移動中間點一步。只需比較該節點的內容和在下降過程中作爲例程參數可用的內容即可。

乾杯&心連心，

Answer 6

這是什麼問我想

bool isPalindrom(node* head) 
{ 
    if(!head) return true; 

    node* left = head; 
    node* mid = head; 

    return cmp(left, mid, head); 
} 

bool cmp(node*& left, node*& mid, node* n) 
{ 
    node* next = n->next; 

    if(next == 0) 
    { 
     node* lprev = left; 
     left = left->next; 
     return lprev->data == n->data;  
    } 

    mid = mid->next; 
    if(next->next == 0) 
    { 
     node* lprev = left; 
     left = left->next->next; 
     return lprev->data == next->data && lprev->next->data == n->data; 
    } 

    if(!cmp(left, mid, next->next)) return false; 

    if(left == mid) return true; 

    if(left->data != next->data) return false; 

    left = left->next; 

    if(left == mid) return true; 

    if(left->data != n->data) return false; 

    left = left->next; 

    return true; 
} 

Answer 7

所以（我粗略idea-請讓我知道） 我們也可以

1）計算LL的長度;
2）適當確定中點
//（對於長度5，中點爲3，但對於長度4，中點爲2）。
3）在中點時 - 將LL從中點移到LL的末尾;
4）比較頭數據和新的中點數據，直到head ref迭代到mid，新的mid ref迭代到NULL。

Answer 8

以下是遞歸代碼，其中節點的數據爲整數，只需將其替換爲char即可。它在O（n）時間內運行，除了隱式使用大小爲O（n）的堆棧之外，使用恆定的空間。其中，n是鏈表中的節點數量。

package linkedList; 
class LinkedList { 
    class LinkedListNode { 
     public int data; 
     public LinkedListNode next; 
     public LinkedListNode (int d) { 
      data = d; 
      next = null; 
     } 
    } 

    class PalinResult { 
     public boolean done; 
     public LinkedListNode forward; 

     public PalinResult (LinkedListNode n) { 
      forward = n; 
      done = false; 
     } 
    } 

    LinkedListNode root; 

    public LinkedList() { 
     root = null; 
    } 

    public LinkedListNode getRoot(){ 
     return root; 
    } 

    public boolean add(int d) { 
     LinkedListNode t = new LinkedListNode (d); 
     if (root == null) { 
      root = t; 
      return true; 
     } 

     LinkedListNode curr = root; 
     while (curr.next != null) { 
      curr = curr.next; 
     } 

     curr.next = t; 
     return true; 
    } 

    /* 
    * Takes O(n time) 
    */ 
    public boolean checkPalindrome() { 
     PalinResult res = new PalinResult (root); 
     return  checkPalindromeRecur(root, res); 
    } 

    private boolean checkPalindromeRecur(LinkedListNode curr, PalinResult res) { 
     if (curr == null) 
      return true; 
     else { 
      boolean ret = checkPalindromeRecur(curr.next, res); 

      if (!ret || (res.done)) 
       return ret; 

      if (curr == res.forward) 
       res.done = true; 

      if (curr.data == res.forward.data) 
       ret = true; 
      else 
       ret = false; 

      res.forward = res.forward.next; 
      return ret; 
     } 
    } 

    public static void main(String args[]){ 
     LinkedList l = new LinkedList(); 
     l.add(1); 
     l.add(4); 
     l.add(1); 

     System.out.println(l.checkPalindrome()); 
    } 
} 

Answer 9

在Java中，此解決方案將比較已讀取的字符串和遞歸的字符串。它不是最好的解決方案，即使它是O（n）它是S（n^2），它應該（至少）使用StringBuffer來減少所有的連接。

它利用包裝類將布爾值與字符串的右側一起傳回。

優點：

1. 只有一個通到列表中，從頭部到結束。
2. 它不需要事先知道列表長度
3. 無需額外的數據結構

缺點：

1. 使用內存S的負載（N^2）
2. 以低效方式連接字符串
3. 遞歸解決方案，速度慢。

代碼：

boolean palindrome(Node n){ 
    RightSide v = palindromeRec(「」, n); 
    return v.palindrome; 
} 

class RightSide{ 
    boolean palindrome; 
    String right; 
} 

private RightSide palindromeRec(String read, Node n){ 
    RightSide v = new RightSide(); 

    if(n == null){ 
     v.palindrome = false; 
     v.right = 「」; 
     return v; 
    } 

    v = palindromeRec(n.value + read, n.next); 

    if(v.palindrome) 
     return v; 
    else if(read.equals(v.right) || (n.value+read).equals(v.right)){ 
     v.palindrome = true; 
     return v; 
    } 

    v.right = n.value + v.right; 
    v.palindrome = false; 

    return v; 
} 

Answer 10

1. 查找總串
2. 獲得具有中期節點的長度（中）位置
3. 打破該節點列表
4. 反向前一半

5. 現在做字符串比較

   include「stdafx.h」

   include「LinkedList。H」

鏈表::鏈表（） { 頭= nullptr; 計數= 0;}

空隙鏈表::的AddItem（字符*數據） { 節點節點=新節點; 節點 - >數據=（空隙）的malloc（strlen的（數據）+ 1）;

strcpy((char*)node->Data, data); 
node->Data = data; 
node->Next = nullptr; 
count++; 

if(head == nullptr) 
{ 
    head = node;   
    head->Next = nullptr; 
    return; 
} 

Node *temp = head; 

while(temp->Next!=nullptr) 
{ 
    temp = temp->Next; 
} 

temp->Next = node; 

}

void LinkedList :: TraverseList（） { Node * temp = head;

while(temp !=nullptr) 
{ 
    printf("%s \n", temp->Data); 
    temp = temp->Next; 
} 

}

節點*鏈表::反向（）{ 如果 （頭||（頭戴式>下一頁）！） { 返回頭; }

Node* temp = head; 

Node* tempN = head->Next; 

Node* prev = nullptr; 

while(tempN) 
{ 
    temp->Next = prev; 

    prev= temp; 
    temp = tempN; 

    tempN = temp->Next; 
} 

temp->Next = prev; 
head = temp; 
return temp; 

}

布爾鏈表:: IsPalindrome（） { INT LEN = 0; Node * temp = head;

while(temp) 
{ 
    len = len + strlen((char*)temp->Data); 
    temp = temp->Next; 
} 

printf("total string length is %d \n", len); 

int i =0; 
int mid1 = 0; 

temp = head; 

while (i < len/2) 
{ 
    int templen = strlen((char*)temp->Data);   

    if(i + strlen((char*)temp->Data) < (len /2)) 
    { 
     i = i + strlen((char*)temp->Data); 
     temp = temp->Next; 
    } 
    else 
    { 
     while(i < len/2) 
     { 
      mid1++; 
      i++; 
     } 

     break; 
    } 
} 

printf("len:%d, i:%d, mid1:%d mid2:%d \n",len, i, mid1, len-mid1); 

Node* secondHalf = temp->Next; 
temp->Next = nullptr; 
Node *firstHalf = Reverse(); 

char* str1 = (char*)malloc(sizeof(char) * mid1 + 1); 
char* str2 = (char*)malloc(sizeof(char) * mid1 + 1); 

memcpy(str1, (char*)firstHalf->Data, mid1); 
str1[mid1] = '\0'; 

int slen = strlen((char*)temp->Data); 

if(slen > mid1) 
{ 
    memcpy(str2, (char*)firstHalf->Data + mid1, slen-mid1); 
    str2[slen-mid1] = '\0'; 
} 
else 
{ 
    str2[0] = '\0'; 
} 

printf("%s, %s", str1, str2); 
str1 = strrev(str1); 

if(!*str2) 
{ 
    str2 = (char*)secondHalf->Data; 
    secondHalf = secondHalf->Next; 
} 

if(*str2 && len%2 == 1) 
{ 
    str2++; 
    if(!*str2) 
    { 
     str2 = (char*)secondHalf->Data; 
     secondHalf = secondHalf->Next; 
    } 
} 

while(*str1 && *str2) 
{ 
    if(*str1 != *str2) 
    { 
     return false; 
    } 

    str1++; 
    str2++; 

    if(!*str1) 
    { 
     retry: 
     firstHalf = firstHalf->Next; 
     if(firstHalf) 
     { 
      str1 = (char*) malloc(strlen((char*)firstHalf->Data) + 1); 
      strcpy(str1,(char*)firstHalf->Data);     
      str1 = strrev(str1); 
     } 

     if(!*str1 && firstHalf) 
     { 
      goto retry; 
     } 
    } 

    if(!*str2) 
    { 
     retrySecondHalf: 
     temp = secondHalf; 
     if(temp) 
     { 
      str2 = (char*)temp->Data;   
      secondHalf = secondHalf->Next; 
     } 

     if(!*str2 && secondHalf) 
     { 
      goto retrySecondHalf; 
     } 
    } 
} 

if(*str1 || *str2) 
{ 
    return false; 
} 

return true; 

}

INT _tmain（INT的argc，_TCHAR * argv的[]）{ 鏈表*列表=新鏈表（）;

list->AddItem(""); 
list->AddItem(""); 
list->AddItem("56"); 
list->AddItem("789"); 
list->AddItem("1"); 
list->AddItem("9"); 
list->AddItem(""); 
list->AddItem(""); 

printf("Is pallindrome: %d \n", list->IsPalindrome()); 

return 0; 

}