检查链表是否是回文

Question

考虑一个链表，其节点是字符，因此链表表示一个字符串。如何编写一个递归程序来检查该字符串是否为回文串？当该程序处理字符串中间的字符时开始卷绕堆栈。例如，假设我的字符串是“madam”，我的递归函数如下：

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

当 currentnode->data == 'd' 时，堆栈必须展开。我被问到了这个问题，目前除了作为一个非常难的谜题外，我无法想到任何用处。

首先的想法是：一种非常明显（但不太优雅）的方法是：

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

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

- PKG

---

除了作为一个非常难的谜题，我想不出这个问题有任何用处。或者作为纯函数式编程入门，其中递归是你唯一拥有的。 - Steve Jessop

好的，这是关于C/C++，而不是Lisp。 - PKG

面试官给了你中点吗？还是字符串/列表的大小？或者至少说过你可以假设前一半的字符是唯一的（在中点之后才有重复）？ - chrisaycock

无需翻译，内容太过抽象。 - PKG

@Ganesh：当然，但是在函数式风格下编写C++是可能的，而这种约束在一定程度上有助于强制执行该风格。 - Steve Jessop

@OP：请注意，递归方法并不是最优解，因为列表可能会非常长，导致堆栈溢出。 - Vlad

Answer 1

“linked list”是指“链表”，您是否指的是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”为止，然后再次反转它，就不需要在递归调用中存储slow的副本：替代地，可以返回一个额外的指针供调用者跟随。不过我不会费力去做这件事。

- Steve Jessop

---

不是 std::list。你不能在单向链表上执行 a--last。 - PKG

如果提问者指定了单链表，那么在问题中可能值得提一下。毕竟这是 C++，而不是 Lisp ;-）无论如何，答案已更新。 - Steve Jessop

即使是单向链表，您也可以执行以下操作。一旦快速运行器到达链表的末尾并且您的慢速运行器位于中间，您可以从头部运行另一个慢速（2）运行器，并将其值与第一个慢速运行器进行比较。时间复杂度将保持为O(n)，而且您不需要使用任何额外的结构，这很好 ;) - Pavel Podlipensky

@PavelPodlipensky，我理解了你的解决方案，如果链表是“abcba”，那么slow1指向c，slow2指向a，即使它是一个链表，这个逻辑仍然会返回false。 - Anshul garg

Answer 2

除了一些棘手的细节，这个问题很容易解决。

首先，通过递归调用移动一个指针一步，但另外两个指针移动两步来找到中点。当两步指针到达末尾时，一步指针就在中间。棘手的问题是：列表长度为偶数还是奇数。

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

祝好运！

- Cheers and hth. - Alf

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

- Zack Bloom

---

哦，是的，我记得自动机类比来自我的计算理论书。谢谢。 - PKG

第二部分(start = start.next; if checkPalin(start, end, stack): return true;)似乎是错误的。它会将"ABB"报告为回文，因为你跳过了'A'。 - Vlad

是的，我把next移到了递归调用旁边，谢谢你发现了它。 - Zack Bloom

我将“Palin”解析为其他内容，这是不好的吗？ - Billy ONeal

起始的 if (start == end) return false; 也应该是错误的，因为一个字母的序列是回文。 - Vlad

@Billy，加入我们吧，面试官也问了这个问题。 - PKG

Answer 4

我想这就是他们所问的内容。

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

- vlad.k.sm

Answer 5

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

- Mariano Latorre

Answer 6

1. 找到字符串的总长度
2. 获取具有中间位置的节点
3. 在该节点处断开列表
4. 反转前半部分

5. 现在进行字符串比较

   包括 "stdafx.h"

   包括 "LinkedList.h"

LinkedList::LinkedList() { head = nullptr; count = 0; }

void LinkedList::AddItem(char* data) { Node node = new Node; node->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() { Node *temp = head;

void LinkedList::遍历列表() { Node *temp = 头节点;

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

}

Node* LinkedList::Reverse() { if(!head || !(head->Next)) { return head; }

节点* 链表::反转() { if(!头 || !(头->下一个)) { 返回 头; }

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;

}

布尔型 LinkedList::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[]) { LinkedList* list = new LinkedList();

主函数(int argc, _TCHAR* argv[]) { LinkedList* list = 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;

}

- Sirisha Chamarthi

Answer 7

这个列表是双向链接的吗？如果是，那么只需要传入起始节点和结束节点，比较它们所指向的内容。如果它们不同，则返回 false。如果它们相同，则递归调用自身并传入 start+1 和 end-1，直到 start > end。

- 500 - Internal Server Error

---

在对@Steve的评论中，楼主表示该列表只是单向链接。 - Vlad

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->next != end) i = i->next; end = i;。
6. 递归，提供新的 start 和 end 的值。

- cdhowie

---

两个问题：O(n^2)的复杂度和未使用中点准则。 - PKG

你的问题中没有提供任何性能标准，因此复杂度不是问题。实际上使用了中点标准——当起始位置等于结束位置时，堆栈将会解开。 - cdhowie

仅仅因为没有指定运行时间，并不意味着O(n^2)的解决方案是一个好的选择。 - Nick Johnson

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

- Tejas

Answer 10

所以（我的大致想法-请告诉我）我们还可以：

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

- gettingthere