检查链接列表是否回文

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; 

}