🌟 前言

Wassup guys！我是Edison 😎

今天是 牛客 上的 nowcoder. OR36 链表的回文结构

Let’s get it！

---

---

1. 题目分析

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

示例 1：

输入：[1，2，4，2，1]
 
返回：true

示例 2：

输入：[1，4，2，1]
 
返回：false

2. 思路分析

这道题很简单：

（1）找到链表的中间节点（奇数就是中间的那个，偶数就是中间的第二个）；
 
（2）从中间节点开始逆置；
 
（3）让前半段和后半段进行比较；

假设我们的链表为：[1，2，4，2，1]（如图所示👇）

第 1 步，定义 快慢指针，找到中间节点（动图演示👇）

注意：这里面找中间节点的方法，要分链表个数为 奇数 还是 偶数，具体可以参考 LeetCode每日一练 —— 876. 链表的中间结点

第 2 步，从 mid’ 开始，逆置后半段（动图演示👇）

注意：这里的逆置可以参考之前做过的一道题，LeetCode每日一练 —— 206. 反转链表

第 3 步，通过一个循环，让 head 节点和 mid 节点依次比较，相等就比较下一个，只要有一个节点为 空，那么就说明结束循环，返回 true（如图所示👇）。

相信到这里大家可能会有个疑惑，它们俩怎么会相等呢？head 走到 2 就结束了呀，而 mid 还要走到 4。

我们知道，链表的当前节点存储的是下一个节点的地址，也就是说从 head 开始，当 head 走到第 2 个节点时，里面存储的 数据 是 2，而存储的 指针 是指向下一个元素的地址，也就是指向 4 的地址；

为什么还能找到 4 的地址呢？

因为我们只对从 mid 开始的 后半段进行逆置 了，前半段又没有逆置，所以当 head 走到第 2 个节点时，里面存储的 数据 是 2，而存储的 指针 是指向下一个节点的地址，也就是数据为 4 的节点的地址（如图所示👇）；

所以比较的过程动图演示👇

3. 代码实现

接口代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    // 1、找到链表的中间节点
    struct ListNode* middleNode(struct ListNode* head){
        struct ListNode* slow, *fast;
        slow = fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    // 2、从中间节点开始, 反转链表
    struct ListNode* reverseList(struct ListNode* head) {
        struct ListNode* cur = head;
        struct ListNode* newHead = NULL;
        while (cur) {
    	   // 头插前保存cur的下一个节点
            struct ListNode* curNext = cur->next;
            // 头插
            cur->next = newHead;
            newHead = cur;
            cur = curNext;
            if (curNext) {
                curNext = curNext->next;
            }
        }
        return newHead;
    }
    
    // 让前半段和后半段进行比较
    bool chkPalindrome(ListNode* A) {
        struct ListNode* head = A;
        struct ListNode* mid = middleNode(head); //找到中间节点
        struct ListNode* newHead = reverseList(mid); //从中间节点开始逆置,并把逆置的结果给newhead
        while (newHead) {
            if (head->val != newHead->val) { //如果原节点的val 不等于 新节点的val
                return false; //返回
            }
            else {
                head = head->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

提交结果