LeetCode 链表的回文结构_回文结构链表 leetcode

链表的回文结构

题目描述

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

示例1
1->2->2->1
示例2
1->2->3->4->5->4->3->2->1
使用语言： C语言

思路解析

回文结构其实就是一个链表关于中间对称，我们可以用快慢指针法求出中间一个数，若为偶数个节点则为中间第二个数，此时慢指针指向的节点即为中间节点，对中间节点到链表的尾进行逆置，再将逆置后的节点和头节点开始一个一个对比，直到一方为空结束

图解如下：

代码实现

class PalindromeList 
{
public:
    bool chkPalindrome(ListNode* A) 
    {   //求中间节点
        ListNode* fast = A;
        ListNode* slow = A;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        //逆置
        ListNode* tem = slow;//保存slow位置，给p
        slow = NULL;//制空slow,因为最后一个节点要指向
        ListNode* p = tem;
        ListNode* p1 = p->next;
        while(p)
        {
            p->next = slow;
            slow = p;
            p = p1;
            //防止p1=NULL还求next
            if(p1)
            {
                p1 = p1->next;
            }
        }
        //判断前后是否相等
        while(A && slow)
        {
            if(A->val == slow->val)
            {
                A = A->next;
                slow = slow->next;
            }
            else
            {
                return false;
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44