【牛客网】链表的回文结构

傷城~ 2023-07-04 03:19 2阅读 0赞

## 题目描述 ##

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。  
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。  
**测试样例：**  
![在这里插入图片描述][20200207153806846.png]

## 解题思路 ##

先使用快慢指针法，设置两个指针fast和slow，遍历链表，fast指针速度是slow指针的两倍，从而找到链表的中间结点。之后将后半截链表逆置。最后从头尾向中间扫描，对比每个元素是否相等，如果都相等，则是回文数，否则不是回文数。

## 完整代码 ##

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/
    class PalindromeList { 
    public:
        bool chkPalindrome(ListNode* A) { 
            if(A == NULL)
                return false;
            else if(A->next == NULL)
                return true;
            //寻找中间结点
            ListNode* fast = A;
            ListNode* slow = A;
            while(fast && fast->next)
            { 
                fast = fast->next->next;
                slow = slow->next;
            }
            //反转链表
            ListNode* prev = NULL;
            ListNode* next;
            while(slow)
            { 
                next = slow->next;
                slow->next = prev;
                prev = slow;
                slow = next;
            }
            //判断是否是回文结构
            while(prev)
            { 
                if(A->val != prev->val)
                    return false;
                else
                { 
                    A = A->next;
                    prev = prev->next;
                }
            }
            return true;
        }
    };

[20200207153806846.png]: https://img-blog.csdnimg.cn/20200207153806846.png