September 24th, 2012 | 
该问题来自于《Cracking the Coding Interview 5th edition》练习题2.7。原题描述如下：“Implement a function to check if a linked list is a palindrome.”我感觉原书给的答案中的递归方法太鬼畜了，没怎么看懂，于是就实现了自己的一个版本。
基本思想就是首先递归到链表尾，然后使用两个指针（一个从链表头向后移动，一个从链表尾向前移动）进行数据比较，并随着弹栈的过程各自移动到下个节点。当两个指针相遇或是错开一格的时候就不用再移动了，直接一溜返回true就行了。我的实现方式中使用了两个指针参数，其中一个还是Node**，好像看起来更鬼畜了……
#include <stdio.h>
typedef struct Node
{
char data;
struct Node *next;
}Node;
bool foo(Node* node, Node** chain, bool* result)
{
*result = false;
if (node == NULL)
{
fprintf(stderr, "error!\n");
return false;
}
else
{
if (node->next == NULL) //到达尾部
{
if ((*chain)->data == node->data)
{
*chain = (*chain)->next;
return true;
}
else
return false;
}
else
{
if (!foo(node->next, chain, result))
return false;
else
{
if (node == *chain || *result) //以后不用再比较了，直接返回
{
*result = true;
return true;
}
else if ((*chain)->data == node->data)
{
if (node == (*chain)->next) //以后不用再比较了，直接返回
*result = true;
else
*chain = (*chain)->next; //继续比较
return true;
}
else
return false;
}
}
}
}
bool IsPalindrome(Node* head)
{
Node* tmp = head;
bool result = false;
foo(head, &head, &result);
return result;
}
int main()
{
Node a1;
a1.data = 'a';
Node a2;
a2.data = 'b';
a1.next = &a2;
Node a3;
a3.data = 'c';
a3.next = NULL;
a2.next = &a3;
Node a4;
a4.data = 'b';
a4.next = NULL;
a3.next = &a4;
Node a5;
a5.data = 'a';
a5.next = NULL;
a4.next = &a5;
bool x = IsPalindrome(&a1);
printf("%d\n", x);
return 0;
}
typedef struct Node
{
char data;
struct Node *next;
}Node;
bool foo(Node* node, Node** chain, bool* result)
{
*result = false;
if (node == NULL)
{
fprintf(stderr, "error!\n");
return false;
}
else
{
if (node->next == NULL) //到达尾部
{
if ((*chain)->data == node->data)
{
*chain = (*chain)->next;
return true;
}
else
return false;
}
else
{
if (!foo(node->next, chain, result))
return false;
else
{
if (node == *chain || *result) //以后不用再比较了，直接返回
{
*result = true;
return true;
}
else if ((*chain)->data == node->data)
{
if (node == (*chain)->next) //以后不用再比较了，直接返回
*result = true;
else
*chain = (*chain)->next; //继续比较
return true;
}
else
return false;
}
}
}
}
bool IsPalindrome(Node* head)
{
Node* tmp = head;
bool result = false;
foo(head, &head, &result);
return result;
}
int main()
{
Node a1;
a1.data = 'a';
Node a2;
a2.data = 'b';
a1.next = &a2;
Node a3;
a3.data = 'c';
a3.next = NULL;
a2.next = &a3;
Node a4;
a4.data = 'b';
a4.next = NULL;
a3.next = &a4;
Node a5;
a5.data = 'a';
a5.next = NULL;
a4.next = &a5;
bool x = IsPalindrome(&a1);
printf("%d\n", x);
return 0;
}
该方法也可以稍作修改以实现逆序一个链表而不需要额外存储空间。
程序使用C语言验证通过。时间复杂度O(n)，不考虑递归本身栈空间的话空间复杂度O(1)。
» 转载请注明来源及链接：未来代码研究所
Posted in 
Tags: 
看了好一会儿才看懂的…你怎么描述你这个递归函数的功能？用栈会好一些吧。
我这个递归函数追求的就是不使用额外的存储空间，只对原始数据本身进行操作。当然用一个栈保存前一半的数据会更好理解，效率也没差多少。总之这道题有N种解法就是了……
其实空间复杂度是一样的，就像快排的空间复杂度是O(logn)一样。