要求

判断一个链表是否为回文结构。

回文结构：

1—2—4—5—4—2—1

1—2—1

1—1

1

思路

将后半部分逆置，并从两端向中间遍历比较。

在这里插入图片描述

找到链表中间结点_思路

快慢指针，快指针每次走2步，慢指针每次走1步，最终慢指针指向的结点就是中间结点。

注：此处我们认为，偶数个结点的情况下，中间结点为中间两个结点的后一个。

在这里插入图片描述

逆置链表

利用前中后3个指针，改变链表的指向。

在这里插入图片描述

逆置了后半部分后，我们将得到类似这样的链表：

在这里插入图片描述

最终只要遍历比较前后两半即可。

最终代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
  public:
    
    /*找到链表的中间结点*/
    struct ListNode* getMiddleNode(struct ListNode* phead) {
        //定义快慢指针
        struct ListNode* slow = phead;
        struct ListNode* fast = phead;

        while (fast) {
            if (fast->next == NULL) {
                break;
            } else {
                slow = slow->next;
                fast = fast->next->next;
            }
        }

        return slow;
    }

    /*逆置链表*/
    struct ListNode* reverseLinkedList(struct ListNode* head) {
        if (head == NULL) { //1.head为空的情况
            return head;
        }
        if (head->next == NULL) { //2.只有1个结点的情况
            return head;
        }
        //3.具有2个及以上个结点的情况
        struct ListNode* cur = head->next;
        struct ListNode* after = cur->next;

        head->next = NULL;
        while (after != NULL) {
            cur->next = head;
            head = cur;
            cur = after;
            after = after->next;
        }
        cur->next = head;
        head = cur;

        return head;
    }

    /*按顺序依次比较两个链表的内容*/
    bool compare_two(struct ListNode* p1, struct ListNode* p2) {
        struct ListNode* cur1 = p1;
        struct ListNode* cur2 = p2;

        while (cur2) {
            if (cur1->val == cur2->val) {
                cur1 = cur1->next;
                cur2 = cur2->next;
            } else {
                return false;
            }
        }

        return true;
    }

    /*判断是否回文的整体逻辑*/
    bool chkPalindrome(ListNode* A) {
        if (A == NULL || A->next == NULL) { //空链表、1个结点的链表，一定不是回文
            return false;
        }

        //1.find the middle node
        struct ListNode* middleNode = getMiddleNode(A);

        //2.reverse the latter part of the list
        struct ListNode* newTail = reverseLinkedList(middleNode);

        //3.traversal and compare the former part and the latter part
        return compare_two(A, newTail);

    }
};