链表问题、合并两个有序链表、链表分区、链表的 Palindromes , 链表相交 - OR36 链表的 Palindromes

题目链接

思路

我们需要找到传入链表的中间结点，并将中间结点及其后面结点进行反转，然后再将原链表的前半部分与反转后的后半部分进行比较，若相同，则该链表是回文结构，否则，不是回文结构。

1.找到链表的中间结点。

2.反转中间结点及其后面的结点。

3.比较链表的前半部分与后半部分的结点值，若相同则是回文结构，否则，不是回文结构。

将A指针指向的结点与RHead指针指向的结点进行比较，若相同，则两个指针后移，继续比较后面的结点，直到RHead指针指向NULL时，比较结束。

注意：就算传入的链表是结点数为奇数的回文结构，该思路也可以成功判断。

class PalindromeList {
public:
    //查找链表的中间结点
    ListNode* middleNode(ListNode* head)
    {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }

        return slow;
    }


    //反转链表
	ListNode* reverseList(ListNode* head)
    {
        ListNode* newhead = nullptr;
        ListNode* cur = head;
        while(cur)
        {
            ListNode* next = cur->next;
            cur->next = newhead;
            newhead = cur;
            cur = next;
        }

        return newhead;
    }

    bool chkPalindrome(ListNode* A) {
        // write code here
        ListNode* mid = middleNode(A);
        ListNode* head = reverseList(mid);
        while(head)
        {
            if(A->val != head->val)
                return false;
            A = A->next;
            head = head->next;
        }
        return true;
    }
};