欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

234.回文链表

程序员文章站 2022-07-15 16:16:43
...

234.回文链表
思路:设置一个快指针和一个慢指针,当快指针走到链表尾部时,慢指针刚好走到链表的中间,具体细节是,但链表节点是偶数个时,链表被分成两个节点个数相等的两部分,当链表节点是奇数个时,链表后一部分比前面一个部分多出一个节点。然后,对后面一半链表进行翻转,再以此进行比较。

代码:

class Solution {
public:
    ListNode* reverse(ListNode* head)
    {
        ListNode* p=NULL,*q=NULL;
        while(head)
        {
            p=head;
            head=head->next;
            p->next=q;
            q=p;
        }
        return q;
    }
    bool isPalindrome(ListNode* head) {
        ListNode* slow=head,*fast=head;
        while(fast&&fast->next)
        {
            fast=fast->next->next;
            slow=slow->next;
        }
        slow=reverse(slow);
        while(head&&slow)
        {
            if(slow->val!=head->val) return false;
            slow=slow->next;
            head=head->next;
        }
        return true;
    }
};

234.回文链表