C语言每日一题(34)链表的回文结构

2024-01-23 15:10:05 浏览数 (1)

牛客网 回文链表

题目描述

描述

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

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

测试样例:

代码语言:javascript复制
1->2->2->1
代码语言:javascript复制
返回:true

思路分析

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

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

代码语言:javascript复制
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;
    }
};

0 人点赞