题解 | #链表的回文结构#

链表的回文结构

https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
*/

class PalindromeList {
  public:
    // 检查链表是否为回文
    bool chkPalindrome(ListNode* A) {
        // 如果链表为空,直接返回 false
        if (A == NULL)
            return false;

        // 使用快慢指针找到链表的中间节点
        ListNode* slow = A, *fast = A;
        while (fast && fast->next) {
            slow = slow->next;         // 慢指针每次移动一步
            fast = fast->next->next;   // 快指针每次移动两步
        }

        // 反转链表的后半部分
        ListNode* cur = NULL, *next = slow;
        while (slow) {
            next = slow->next;    // 暂存下一个节点
            slow->next =
                cur;     // 将当前节点的 next 指向前一个节点,完成反转
            cur = slow;           // 更新前一个节点为当前节点
            slow = next;          // 将当前节点移动到下一个节点
        }

        // 将next指针重新指向链表的头部,用于从头开始比较
        next = A;

        // 比较前半部分和反转后的后半部分的节点值
        while (cur) {
            if (next->val != cur->val) // 若节点值不相同,说明不是回文
                return false;
            next = next->next;         // 移动到下一个节点
            cur = cur->next;           // 反转部分也移动到下一个节点
        }

        // 若所有节点值都匹配,则链表为回文,返回 true
        return true;
    }
};

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-08 14:10
点赞 评论 收藏
分享
每晚夜里独自颤抖:要求太多的没必要理
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务