007、链表的回文结构

0、题目描述

链表回文结构

1、法1

一个复杂的问题可以拆解成几个简单的问题，找中间节点和逆置链表（翻转链表）之前都做过。

class PalindromeList {
public:
	//1、找中间节点
    ListNode* FindMid(ListNode* A)
    {
        if (A == nullptr || A->next == nullptr)
        {
            return A;
        }
        ListNode* fast = A;
        ListNode* slow = A;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
	//2、翻转链表
    ListNode* ReverseList(ListNode* phead)
    {
        ListNode* cur = phead;
        ListNode* newhead = nullptr;
        while (cur)
        {
            ListNode* next = cur->next;
            cur->next = newhead;
            newhead = cur;
            cur = next;
        }
        return newhead;
    }

    bool chkPalindrome(ListNode* A) 
    {   
        ListNode* mid = FindMid(A);
        ListNode* B = ReverseList(mid);
        //3、依次比对
        while (A && B)
        {
            if (A->val != B->val)
            {
                return false;
            }
            A = A->next;
            B = B->next;
        }
        return true;
    }
};