C语言每日一题（34）链表的回文结构

牛客网 回文链表

题目描述

描述

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：

1->2->2->1

返回：true

思路分析

找到链表的中间结点，将中间结点后的链表进行逆置，一个从头开始遍历到中间结点，一个从中间结点遍历到尾结点进行匹配，如果存在值不相等的就不是回文链表。

对于存在的结点个数为奇数或偶数的情况，当找到中间结点并进行逆置时，偶数情况下则是正常情况，奇数情况下，中间结点逆置后，它的前驱结点的next值依然指向逆置后的中间结点，不影响遍历。

class PalindromeList {
  public:
    struct ListNode* middleNode(struct ListNode* head) {//取中间结点
        struct ListNode* slow = head;
        struct ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
 
    }
    struct ListNode* ReverseList(struct ListNode* head ) {//逆置链表
        struct ListNode* pre = NULL;
        struct ListNode* cur = head;
        struct ListNode* nex = cur->next;
        while (cur != NULL) {
            cur->next = pre;
            pre = cur;
            cur = nex;
            nex = cur->next;
        }
        return pre;
    }
    bool chkPalindrome(ListNode* A) {//进行判断
        ListNode* middle=middleNode(A);
        ListNode* rev=ReverseList(middle);
        ListNode* cur=A;
        while(cur&&rev)
        {
            if(cur->val!=rev->val)
            {
                return false;
            }
            cur=cur->next;
            rev=rev->next;
        }
        return true;
    }
};