algorithm - 在链表中查找回文

Question

这是一个面试问题（再次）。

给定一个单连接链表，找出链表中最大的回文数。（你可以假设回文的长度是偶数）

我采用的第一种方法是使用堆栈——我们从一开始就遍历列表并不断推入字母。每当我们发现堆栈顶部的字母与链表上的下一个字母相同时，开始弹出（并增加链表指针）并设置匹配的字母数。在我们发现不匹配后，将您从堆栈中弹出的所有字母推回，并继续您的推入和弹出操作。这种方法的最坏情况复杂度将是 O(n2) 例如，当链表只是相同字母的字符串时。

为了提高空间和时间复杂度（通过一些常数因素），我建议将链表复制到一个数组中，并在数组中找到最大的回文数，这又需要 O(n2) 时间复杂度和 O(n) 空间复杂度。

有什么更好的方法可以帮助我吗？:(

Answer 1

可以想出一个空间复杂度为 O(1) 的 O(n²) 算法，如下所示：

考虑f→o→b→a→r→r→a→b：

在访问时遍历列表反转链接。x=f从和开始y=f.next：

• 放x.next = null

• fo→b→a→r→r→a→b
  ^ ^
  | \
  xy

  并检查两个列表（x 和 y）相等的链接数。
• 现在继续。( tmp=y.next, y.next=x, x=y, y=tmp) 例如，在第二步中，它将产生f←o b→a→r→r→a→b,x=o和y=b，现在您再次检查它是否是回文并继续：
• f←o←b a→r→r→a→b
• f←o←b←a r→r→a→b
• f←o←b←a←r r→a→b耶 ：）
• 等等

如果您需要再次恢复列表，请在 O(n) 中再次反转它

Answer 2

这是一个经过充分分析的O(N)时间复杂度问题。

• 您可以反转原始字符串（比如说strand str_reversed）

那么问题就转化为：在和中找到最长的公共子串。strstr_reversed

• O(N) 方法是构建具有恒定时间最低共同祖先检索的后缀树 (O(N))。

Answer 3

如果将列表复制到数组中，以下内容可能会很有用：由于我们只考虑偶数长度回文，我假设这种情况。但是该技术可以很容易地扩展到奇数长度回文的工作。

我们存储的不是回文的实际长度，而是长度的一半，因此我们知道可以向左/向右移动多少个字符。

考虑这个词：aabbabbabab。我们正在寻找最长的回文。

a a b b a b b a b a b (spaces for readability)
°^°                   start at this position and look to the left/right as long as possible,
 1                    we find a palindrome of length 2 (but we store "1")
                      we now have a mismatch so we move the pointer one step further
a a b b a b b a b a b
   ^                  we see that there's no palindrome at this position, 
 1 0                  so we store "0", and move the pointer
a a b b a b b a b a b
  ° °^° °             we have a palindrome of length 4, 
 1 0 2                so we store "2"
                      naively, we would move the pointer one step to the right,
                      but we know that the two letters before pointer were *no*
                      palindrome. This means, the two letters after pointer are
                      *no* palindrome as well. Thus, we can skip this position
a a b b a b b a b a b
         ^            we skipped a position, since we know that there is no palindrome
 1 0 2 0 0            we find no palindrome at this position, so we set "0" and move on
a a b b a b b a b a b
      ° ° °^° ° °     finding a palindrome of length 6,
 1 0 2 0 0 3 0 0      we store "3" and "mirror" the palindrome-length-table
a a b b a b b a b a b
                 ^    due to the fact that the previous two positions hold "0", 
 1 0 2 0 0 3 0 0 0    we can skip 2 pointer-positions and update the table
a a b b a b b a b a b
                   ^  now, we are done
 1 0 2 0 0 3 0 0 0 0

这意味着：一旦我们找到回文位置，我们就可以推断出表格的某些部分。

另一个例子：aaaaaab

a a a a a a b
°^°
 1

a a a a a a b
° °^° °
 1 2 1        we can fill in the new "1" since we found a palindrome, thus mirroring the
              palindrome-length-table
a a A A a a b (capitals are just for emphasis)
     ^        at this point, we already know that there *must* be a palindrome of length
 1 2 1        at least 1, so we don't compare the two marked A's!, but start at the two 
              lower-case a's

我的观点是：一旦我们找到回文，我们就可以镜像（至少一部分）回文长度表，从而推断出有关新字符的信息。这样，我们可以保存比较。

Answer 4

这是一个 O(n^2) 算法：

1. 将列表转换为双向链表

2. 要获得均匀长度的回文，您需要两个相同的字母彼此相邻。所以迭代每对相邻的字母（其中 n-1 个），并且在每次迭代中，如果字母相同，则找到中间字母是这两个字母的最大回文。

Answer 5

我通过在 O(n) 时间内使用递归来做到这一点。我这样做是通过，

1. 假设我们有一个源链表，现在将整个链表复制到另一个链表，即目标链表；
2. 现在反转目标链表；
3. 现在检查源链表和目标链表中的数据是否相等，如果相等则为回文，否则为非回文。
4. 现在释放目标链表。

代码：

#include<stdio.h>
#include<malloc.h>

struct node {
    int data;
    struct node *link;
};

int append_source(struct node **source,int num) {
    struct node *temp,*r;
    temp = *source;
    if(temp == NULL) {
        temp = (struct node *) malloc(sizeof(struct node));
        temp->data = num;
        temp->link = NULL;
        *source = temp;
        return 0;
    }
    while(temp->link != NULL) 
        temp = temp->link;
    r = (struct node *) malloc(sizeof(struct node));
    r->data = num;
    temp->link = r;
    r->link = NULL;
    return 0;
}

int display(struct node *source) {
    struct node *temp = source;
    while(temp != NULL) {
        printf("list data = %d\n",temp->data);
        temp = temp->link;
    }
    return 0;
}

int copy_list(struct node **source, struct node **target) {
    struct node *sou = *source,*temp = *target,*r;
    while(sou != NULL) {
        if(temp == NULL) {
            temp = (struct node *) malloc(sizeof(struct node));
            temp->data = sou->data;
            temp->link = NULL;
            *target = temp;
        }
        else {
            while(temp->link != NULL) 
                temp = temp->link;
            r = (struct node *) malloc(sizeof(struct node));
            r->data = sou->data;
            temp->link = r;
            r->link = NULL;
        }
        sou = sou->link;
    }
    return 0;
}

int reverse_list(struct node **target) {
    struct node *head = *target,*next,*cursor = NULL;
    while(head != NULL) {
        next = head->link;
        head->link = cursor;
        cursor = head;
        head = next;
    }
    (*target) = cursor;
    return 0;
}

int check_pal(struct node **source, struct node **target) {
    struct node *sou = *source,*tar = *target;
    while( (sou) && (tar) ) {
        if(sou->data != tar->data) {
            printf("given linked list not a palindrome\n");
            return 0;
        }
        sou = sou->link;
        tar = tar->link;
    }
    printf("given string is a palindrome\n");
    return 0;
}

int remove_list(struct node *target) {
    struct node *temp;
    while(target != NULL) {
        temp = target;
        target = target->link;
        free(temp);
    }
    return 0;
}

int main()
{
    struct node *source = NULL, *target = NULL;
    append_source(&source,1);
    append_source(&source,2);
    append_source(&source,1);
    display(source);
    copy_list(&source, &target);
    display(target);
    reverse_list(&target);
    printf("list reversed\n");
    display(target);
    check_pal(&source,&target); 
    remove_list(target);
    return 0;
}

Answer 6

首先找到链表的中点，为此遍历链表并统计节点数。

假设节点数为 N，中点为 N/2。

现在遍历到中点节点并开始反转链表直到结束，这可以用 O(n) 复杂度完成。

然后比较从开始到中点的元素与从中点到最后的元素，如果它们都相等，则字符串是回文，否则中断。

时间复杂度：- O(n)

空间复杂度：- O(1)