本文共 1235 字，大约阅读时间需要 4 分钟。

为了判断链表是否为回文结构，可以使用以下方法：

   
题目描述
对于一个链表，请设计一个时间复杂度为O(n)，额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
   
解题思路
使用快慢指针反转链表，然后比较原链表和反转后的链表是否相等。
   
class PalindromeList {    public:        bool chkPalindrome(ListNode* A) {            if (A == NULL || A->next == NULL) return true;            ListNode* slow = A;            ListNode* fast = A;            ListNode* prev = NULL;            while (fast && fast->next) {                prev = slow;                slow = slow->next;                fast = fast->next->next;            }            if (fast != NULL && fast->val != A->val) return false;            if (prev != NULL) prev->next = NULL;            ListNode* newhead = NULL, *cur = slow;            while (cur) {                ListNode* next = cur->next;                cur->next = newhead;                newhead = cur;                cur = next;            }            slow = newhead;            while (A) {                if (A->val != slow->val) return false;                A = A->next;                slow = slow->next;            }            return true;        }}
   
这个方法的时间复杂度是O(n)，额外空间复杂度为O(1)。通过快慢指针反转链表，防止链表成环，然后比较原链表和反转后的链表是否相等来判断是否为回文结构。

转载地址：http://asbb.baihongyu.com/