牛客_OR36 链表的回文结构

目录

一、题目

二、解题思路

三、解题代码

---

一、题目

题目链接：链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

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

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

测试样例：

二、解题思路

先找到中间节点：然后再将在中间节点后面的节点逆置：然后再将逆置后的节点和原链表开始同时比较遍历。

bool chkPalindrome(ListNode* A) {
        // write code here
        // 找中间节点
        ListNode* head = A;
        ListNode* rhead = FoundMid(head);
        
        // 逆置后半部分
        rhead = realse(rhead);
        
        // 遍历比较
        while (rhead)
        {
            if (rhead->val != head->val)
            {
                return false;
            }
            rhead = rhead->next;
            head = head->next;
        }
        
        return true;
    }

三、解题代码

    // 找中间节点
    ListNode* FoundMid(ListNode* head)
    {
        ListNode* fast = head;
        ListNode* slow = head;
        
        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        
        return slow;
    }
    // 逆置
    ListNode* realse(ListNode* head)
    {
        assert(head);
        
        ListNode* cur = head;
        ListNode* prev = NULL;
        ListNode* next = cur->next;
        
        while (cur)
        {
            cur->next = prev;
            prev = cur;
            cur = next;
            if (next != NULL)
                next = next->next;
        }
        
        return prev;
    }
    bool chkPalindrome(ListNode* A) {
        // write code here
        // 找中间节点
        ListNode* head = A;
        ListNode* rhead = FoundMid(head);
        
        // 逆置后半部分
        rhead = realse(rhead);
        
        // 遍历比较
        while (rhead)
        {
            if (rhead->val != head->val)
            {
                return false;
            }
            rhead = rhead->next;
            head = head->next;
        }
        
        return true;
    }