关关的刷题日记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;
    }
};

照顾好自己的身体，控制好自己的情绪，加油！

以上就是关关关于这道题的总结经验，希望大家能够理解，有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390，也可以加入专知——Leetcode刷题交流群（请先加微信小助手weixinhao: Rancho_Fang）。 同时请，关注我们的公众号，获取最新关于专知以及人工智能的资讯、技术、算法等内容。扫一扫下方关注我们的微信公众号。