检查链表是否是回文

Question

考虑一个节点为字符的链表，因此该列表表示一个字符串。如何编写一个递归例程来检查字符串是否是回文，以便 所述函数在处理字符串中间的字符时开始展开堆栈？

例如，假设我的字符串是“madam”。我的递归函数如下所示：

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

当 currentnode->data == 'd '，堆栈必须展开。

我在接受采访时被问到这个问题；目前我想不出这个问题有什么用处，除非它是一个非常难的谜题。

第一个想法：一个非常明显（如果不优雅）的方法是：

1. 首先计算列表的中点。
2. 如果 currentnode 位于 midpoint “之前”，则手动将前者推入堆栈。这可以通过维护一个计数器来决定。
3. 否则，在递归的每一步中展开手动维护的堆栈，并与当前字符进行比较。

有更好的想法或新见解吗？

Answer 1

“链表”是指 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());

我利用了这样一个事实：可以从末尾迭代，也可以从头向前迭代。目前尚不清楚问题是否给出了这一点。

使用单链表，您可以运行两个迭代器，一个快，一个慢。每次调用时，将快的递增两次，将慢的递增一次。当快的列表到达列表末尾时，慢的列表位于中点（嗯，+/- 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 2

模数棘手的细节这个很简单。

首先，通过递归调用将一个指针仅移动一步，然后移动另外两步来找到中点。当两步指针到达末端时，一步指针位于中间。棘手的事情：偶数与奇数长度列表。

然后后退（从递归调用返回），并在后退时将中指针向前移动一步以进行每次返回。只需将该节点的内容与下降期间可用作常规参数的内容进行比较即可。

干杯&呵呵，

Answer 3

如果您确实想使用堆栈，这是使用非确定性下推自动机的计算理论的常见练习。这个想法是将每个字符推入堆栈，并在每个字符处进行分支，一个分支跳过一个字符（如果它是一个奇怪的回文）并将每个字符从堆栈中弹出，同时将其与列表其余部分中的一个进行比较，另一个分支执行相同操作，但不跳过该初始字符（如果它是偶数回文），第三个分支继续向堆栈添加元素（并使用下一个字符再次递归地开始分支）。这三个分支可以通过将堆栈的当前状态递归地传递到每个分支来表示。

在伪代码中：

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 4

该列表是双向链接的吗？然后就是传入起始节点和结束节点，比较它们指向的内容。如果不同，则返回 false。如果它们相同，则使用 start+1 和 end-1 递归调用自己，直到 start > 。结尾。

Answer 5

这就是我所问的问题

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 6

在 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 7

1. 找到整个字符串的长度
2. 获取具有中间（中间）位置的节点
3. 在该节点处打破列表
4. 反转前半部分

5. 现在进行字符串比较

   包含“stdafx.h”

   include "LinkedList.h"

LinkedList::LinkedList()
{
头=空指针；
计数=0；
}

void LinkedList::AddItem(char* 数据)
{
节点节点=新节点;
节点->Data = (void) malloc(strlen(data) + 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()
{
节点 *temp = 头；

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

}

节点* LinkedList::Reverse()
{
if(!head || !(head->Next))
{
返回头；
LinkedList

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;

bool

::IsPalindrome()
{
int 长度 = 0;
节点*温度=头；

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[])
{
LinkedList* 列表 = new LinkedList();

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

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

return 0;

}

Answer 8

首先，迭代到列表的末尾并将指向最后一个节点的指针存储为 end。然后将指向第一个节点的指针存储为start。

然后，调用函数并提供这些值。该函数将：

1. 测试是否 start == end （它们指向相同的链接）。如果是，它将立即返回 true。 （列表中有奇数个项目，中间的项目是唯一剩下的。）
2. 然后它将查看 start 和 end 表示的值。如果不相等，则立即返回 false。 （不是回文。）
3. 否则，它将更改 start 以指向下一个链接（大概是 start = start->next）。
4. 如果 start == end，则立即返回 true（处理列表中链接数量为偶数的情况）。
5. 找到 end 之前的链接并将 end 设置为它： link i = start; while (i->下一个!=结束) i = i->下一个;结束=我；。
6. 递归，为 start 和 end 提供新值。

Answer 9

以下是递归代码，其中节点的数据为整数，只需将其替换为字符即可。它在 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 10

所以（我的粗略想法-请告诉我）
我们还可以

1）计算LL的长度；
2）适当确定中点
//（对于长度 5，中点为 3，但对于长度 4，中点为 2）。
3) 当在中点时-将 LL 从中点反转到 LL 的末端；
4) 将 head 数据与新的中点数据进行比较，直到 head 引用迭代到 mid 并且新的 mid 引用迭代到 NULL。