该问题来自于《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;
}

该方法也可以稍作修改以实现逆序一个链表而不需要额外存储空间。

程序使用C语言验证通过。时间复杂度O(n),不考虑递归本身栈空间的话空间复杂度O(1)。

» 转载请注明来源及链接:未来代码研究所

Related Posts:

3 Responses to “使用递归方法检测回文链表”

  • rockuw says:

    看了好一会儿才看懂的…你怎么描述你这个递归函数的功能?用栈会好一些吧。

    • 暗影吉他手 says:

      我这个递归函数追求的就是不使用额外的存储空间,只对原始数据本身进行操作。当然用一个栈保存前一半的数据会更好理解,效率也没差多少。总之这道题有N种解法就是了……

Leave a Reply

World Line
Time Machine
Friendly Links
Online Tools