这是一道面试题(又来了)。
给定一个单向链表，请找出其中最大的回文字符串。(你可以假设回文字符串长度为偶数)
我提出的第一种方法是使用栈——我们从链表的头部开始遍历，并将字母压入栈中。每当我们发现栈顶的字母与链表中的下一个字母相同时，开始弹出(并增加链表指针)并计算匹配的字母数量。在找到不匹配时，将从栈中弹出的所有字母推回去，继续进行压入和弹出操作。这种方法的最坏时间复杂度为O(n2)，例如当链表只是由相同字母组成的字符串时。
为了提高空间和时间复杂度(通过某些常数因子)，我提出了将链表复制到数组中，在数组中查找最大大小的回文字符串，这也需要O(n2)的时间复杂度和O(n)的空间复杂度。
有更好的方法可以帮助我吗？ :(
f→o→b→a→r→r→a→b：x=f 和 y=f.next 开始:
x.next = nullf o→b→a→r→r→a→b ^ ^ | \ x y并检查有多少个链接是两个列表（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→bf←o←b←a r→r→a→bf←o←b←a←r r→a→b 没错 :)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
我使用递归在O(n)时间内完成了它。
我是这样做的：
代码：
#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;
}
这里有一个O(n^2)的算法：
将列表转换为双向链表
为了得到一个偶数长度的回文，你需要有两个相同的字母相邻。 因此，遍历每一对相邻字母（共n-1对），在每次迭代中，如果字母相同，则找到以这两个字母为中心的最大回文。
首先找到链表的中点，遍历整个链表并计算节点数。
假设节点数为N，则中点为N/2。
现在从头开始遍历链表直到中点节点，并从中点开始反转链表，直到链表末尾。这可以在O(n)的时间内完成。
然后将从开头到中点的元素与从中点到最后的元素进行比较，如果它们都相等，则字符串是回文的，否则跳出循环。
时间复杂度：O(n)
空间复杂度：O(1)