关关的刷题日记76 – Leetcode 234. Palindrome Linked List- 专知

会员服务 ·

关关的刷题日记76 – Leetcode 234. Palindrome Linked List

关关

点击上方“专知”，关注获取专业AI知识”

关关的刷题日记76 – Leetcode 234. 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?

题目给定一个链表，让我们判断是否是回文。能否用线性时间复杂度，不开辟额外空间来实现？

思路

因为链表只能通过前一个节点找到后一个节点，所以没办法像数组或者字符串那样设置头尾双重指针同时向中间遍历来判断是否是回文。然后最简单的想法是把链表的值放到一个数组里，判断是否是回文，不过题目要求不能开辟额外空间，这种方法也行不通了。然后怎么能在不开辟额外空间的情况下来判断链表是否是回文呢？我们是需要从后往前遍历节点的，但是链表又只能从前往后找节点，所以我们可以先将链表后半段进行转置，然后再比较前半段和转置后的后半段来判断是否是回文。转置链表大家可以参考关关的刷题日记70 – Leetcode 206. Reverse Linked List，如何将链表分成两段：设置快慢指针，快指针到尾巴的时候，慢指针就是后半段的开头。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head==nullptr)
            return true;
        ListNode* fast, *slow, *p, *q, *r, *flag;

        //设置快慢指针，找到链表后半段开头
        fast=head;
        slow=head;
        while(fast!=nullptr && fast->next!=nullptr)
        {
            fast=fast->next->next;
            slow=slow->next;
        }

        //将链表后半段转置
        p=slow;
        q=p->next;
        while(q!=nullptr)
        {
            r=q->next;
            q->next=p;
            p=q;
            q=r;
        }
        slow->next=nullptr;
        slow=p;

        //比较链表前半段和转置后的后半段，来判断是否是回文
        while(slow!=nullptr)
        {
            if(slow->val!=head->val)
                return false;
            slow=slow->next;
            head=head->next;
        }
        return true;
    }
};