LeetCode - 234. 回文链表

问题

234. 回文链表 - 力扣（LeetCode）

思路

首先，我需要找到链表的中点，这里使用快慢指针技巧 - slow指针每次走一步，fast指针每次走两步。当fast到达链表尾部时，slow就正好在中间位置。

然后关键的一步是处理链表长度的奇偶性:

• 如果fast不为空，说明链表长度是奇数，这时中间节点不应该参与比较，所以我从slow的下一个节点开始反转

• 如果fast为空，说明链表长度是偶数，直接从slow开始反转后半部分

接着我用递归方式反转后半部分链表 - 递归到链表末尾，然后在回溯过程中重新连接指针，把方向反过来。

最后，比较原链表前半部分与反转后的后半部分，如果它们对应位置的值都相同，那么这就是一个回文链表。

这个算法的时间复杂度是O(n)，我们只需要遍历链表常数次。空间复杂度主要来自递归调用栈，是O(n/2)，也就是O(n)

读者可能出现的错误写法

class Solution {
public:
    bool isPalindrome(ListNode* head) 
    {
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode newlist = reserve(slow->next);
        bool result = compare(head,newlist);
        return result;
    }
    ListNode* reserve(ListNode* head)
    {
        if(!head || !head->next)
        {
            return head;
        }

        ListNode* newHead = reserve(head->next);
        head->next->next = head;
        head->next = nullptr;

        return newHead;
    }

    bool compare(ListNode* head1,ListNode* head2)
    {
        while(head1&&head2)
        {
            if(head1->val == head2->val)
            {
                head1 = head1->next;
                head2 = head2->next;
            }
            else
            {
                return false;
            }
        }
        return true;
    }
}; 

这个方法有一个问题，对于奇数长度的链表会出错。

问题在于：当链表长度为奇数时，中间节点不应该参与比较。但你的代码中，直接反转了从中点开始的所有节点，导致前半部分比后半部分多出节点。也就是说，当快慢指针走完之后，需要进行判断是否是奇数，如果是奇数就直接跳过slow->next，如果不是奇数就使用slow

正确写法

class Solution {
public:
    bool isPalindrome(ListNode* head) 
    {
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* newlist = nullptr;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        if(fast)
        {
            newlist = reserve(slow->next);
        }
        else
        {
            newlist = reserve(slow);
        }
        bool result = compare(head,newlist);
        return result;
    }
    ListNode* reserve(ListNode* head)
    {
        if(!head || !head->next)
        {
            return head;
        }

        ListNode* newHead = reserve(head->next);
        head->next->next = head;
        head->next = nullptr;

        return newHead;
    }

    bool compare(ListNode* head1,ListNode* head2)
    {
        while(head1 && head2)
        {
            if(head1->val == head2->val)
            {
                head1 = head1->next;
                head2 = head2->next;
            }
            else
            {
                return false;
            }
        }
        return true;
    }
};