234 - Palindrome Linked List

Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

Hide Tags

 Linked List Two Pointers

Hide Similar Problems

 (E) Palindrome Number (E) Valid Palindrome (E) Reverse Linked List

比较容易想到的是用栈，但是空间不是常量。

最正确的思路应该是找到中点，翻转后半部分的链表，然后逐个比较前后半部分。

另外一个比较好玩的思路是用递归，用前后半部分的起始节点指针作为参数。

每次退出深一层的递归调用，前半部分会自然回退到上一个节点，所以只需要把后半部分的节点向前推进就好了。

递归的终止条件是找到中间的两个点，他们可能是相邻，也可能隔着一个（如果整个链表总共有奇数个节点）。

当然严格意义上递归的空间开销并不是常量的，所以。。。还是翻转吧。

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

    bool isPalindrome(ListNode* head) {

        if(head&&(head->next))

        {

            if(head->next->next)

            {

                ListNode* fast=head;

                ListNode* slow=head;

                while(fast && (fast->next))

                {

                    slow = slow->next;

                    fast = fast->next->next;

                }

                int odd=0;

                if(fast)

                    slow = slow->next, odd = 1;

                return check(head, slow, odd);

            }

            else

                return ((head->val)==(head->next->val));

        }

        

        return true;

    }

    

    bool check(ListNode* first, ListNode*& second, int odd)

    {

        if((!odd && (second != (first->next))) || (odd && (second != (first->next->next))) )

            if(false == check(first->next, second, odd))

                return false;

        bool rst = ((first->val)==(second->val));

        second = second->next;

        return rst;

    }

};