[LeetCode]234. 回文链表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

思路:

这是一道简单难度的题，看见判断回文，首先想到试着用栈来暂存前半部分字符然后与后半部分字符对比，数字相同则出栈，如果能够空栈则一定是偶数个节点的回文链表，如果剩一个则是奇数个节点的链表。似乎这样不必扫描多次链表，但这种做法根本无法分辨1->2->3->2->1和 3-> 1->2->2->1这两种情况，所以必须找到链表的中点在何处。而且这个思路同” 建立一个list，然后将链表中的数存进去，然后判断这个list是否回文 ” 以及建立Hash表检查是否存在的思路一样，无法无法满足O(1) 的空间复杂度。

因此采取“先找到中点然后反转后半部分链表，再从头部和中点开始扫描链表对比是否节点值相同”的思路。找到中点依靠快慢指针即可，快指针一次循环前进两个节点慢指针一次前进一个节点，这样当循环结束时，慢指针一定会停在中点节点(奇数个节点情形)或是前半部分的最后一个节点上(偶数个节点情形)，可以依靠快指针指向节点的下一个节点是否存在来判断上述情形：如果快指针的下一个节点存在则说明共有偶数个节点，慢指针停在前半部分的最后一个节点上；如果快指针的下一个节点不存在，则说明共有奇数个节点，慢指针停在中点节点上。

至于反转链表，使用类似头插法的方式完成即可。不过要注意，慢指针指向的节点其next域总是指向已经反转的部分链表的最后一个节点，例如 1->2->3->4->3->2->1翻转后会变成 1->2->3->4->3<-2<-1 ，此时应注意一下循环的结束条件。

AC代码:

/**
 * 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 == nullptr)
            return true;
        ListNode* fastCursor = head;
        ListNode* slowCursor = head;
        while(fastCursor->next != nullptr && fastCursor->next->next != nullptr)
        {
            fastCursor = fastCursor->next->next;
            slowCursor = slowCursor->next;
        }
        if(fastCursor->next != nullptr)
        {
            ListNode* ReversedHead = slowCursor->next;
            slowCursor->next = nullptr;
            ReversedHead = ReverseList(ReversedHead);
            while(head != nullptr && ReversedHead != nullptr)
            {
                if(head->val != ReversedHead->val)
                    return false;
                head = head->next;
                ReversedHead = ReversedHead->next;
            }
            return true;
        }
        else
        {
            ListNode* ReversedHead = slowCursor->next;
            ReversedHead = ReverseList(ReversedHead);
            while(head != slowCursor && ReversedHead != nullptr)
            {
                if(head->val != ReversedHead->val)
                    return false;
                head = head->next;
                ReversedHead = ReversedHead->next;
            }
            return true;
        }
    }
    ListNode* ReverseList(ListNode* head)
    {
        ListNode* cur = NULL;
        while (head) {
            ListNode* nextNode = head -> next;
            head -> next = cur;
            cur = head;
            head = nextNode;
        }
        return cur;
    }
};

[LeetCode]234. 回文链表

Published by

WiiGe