链表的回文结构（详解）

链表的回文结构（详解）

题目：

链表的回文结构

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

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

测试样例：

1->2->2->1
返回：true
1
2

思路：

1. 我们想要通过对比链表的前一半和链表的后一半是否相同来判断是否为回文结构

2. 那我们就要找到中间节点，也就是快慢指针法

3. 

4. 不仅如此，我们还要通过prev来记录slow的前一个节点，这样我们在后面需要对prev进行断联，我们才得到该节点

5. 

6. 这个时候将slow节点和之后的节点进行逆置，创建一个新链表，让slow节点和之后的节点依次头插到新链表当中

7. 

8. 逆置完链表之后，要记得让slow节点之前的节点断联 ，也就是prev->next = NULL

9. 然后就是遍历原链表 判断两个链表的val值是否相等，不相等返回false，相等返回true

代码：

struct ListNode {
    int val;
    struct ListNode* next;
};

typedef struct ListNode ListNode;
bool chkPalindrome(ListNode* A)
{
    // 创建快慢指针，去找到链表的中间节点
    ListNode* slow, * fast;
    slow = fast = A;

    // 创建一个prev指针去专门指向slow的前一个节点 最终找到的是中间节点的前一个节点
    ListNode* prev = A;

    // 找到中间节点  2slow = fast
    while (fast && fast->next)
    {
        prev = slow; // 指向slow的前一个节点
        slow = slow->next;
        fast = fast->next->next;

    }

    // 此时slow就是A链表的中间节点
    // 这个时候我们逆置slow节点后面的节点
    // 如果和slow节点前面的节点一样，那就是回文结构

    // 创建新链表
    ListNode* newhead = NULL;

    // 将slow节点及以后的节点逆置
    // 也就是让后面的节点依次头插到新链表中
    ListNode* pcur = slow;
    while (pcur)
    {
        ListNode* next = pcur->next; // 让next记载pcur的下一个节点
        pcur->next = newhead; // 让pcur头插到新链表中

        newhead = pcur; // 更新第一个节点
        pcur = next; // 让pcur继续向后遍历
    }
    // 走到这里 slow及slow后面的节点都逆置完毕了
    // 但是有一个需要注意的地方，我们的slow的前一个节点仍然指向的是slow节点
    // 但是我们又新创建了一个逆置链表，那么prev此时的next指针指向的就是逆置链表的尾节点
    // 因此我们需要将prev不在指向slow节点，而是NULL
    prev->next = NULL;

    // 这个时候我们去判断 新链表是否和 A链表第一个节点到slow节点之前相等
    ListNode* cur = A;
    while (cur)
    {
        // 判断原链表和新链表的val值是否相同
        if (cur->val != newhead->val)
            return false; // 不同就返回false
        cur = cur->next; //相同就继续往下走
        newhead = newhead->next;
    }
    // 走到这里说明是回文结构了

    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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62