Daily practice of LeetCode - palindrome structure of OR36 linked list

前言

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）找到链表的中间节点（The odd number is the one in the middle,An even number is the second in the middle）;
 
（2）Invert from the middle node;
 
（3）Let the first half and the second half compare;

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

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

注意：Here's how to find an intermediate node,The number of linked lists to be divided is 奇数 还是 偶数,具体可以参考 LeetCode每日一练 —— 876. 链表的中间结点

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

注意：The inversion here can refer to a question that was done before,LeetCode每日一练 —— 206. 反转链表

第 3 步,通过一个循环,让 head 节点和 mid Nodes are compared in turn,相等就比较下一个,As long as there is a node for 空,Then the cycle ends,返回 true（如图所示）.

I believe that everyone here may have doubts,How can they be equal？head 走到 2 It's over,而 mid still to go 4.

我们知道,The current node of the linked list stores the address of the next node,也就是说从 head 开始,当 head 走到第 2 个节点时,里面存储的 数据 是 2,而存储的 指针 是指向下一个元素的地址,也就是指向 4 的地址;

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

Because we only follow mid 开始的 The second half is reversed 了,No reversal in the first half,所以当 head 走到第 2 个节点时,里面存储的 数据 是 2,而存储的 指针 is the address to point to the next node,That is, the data is 4 的节点的地址（如图所示）;

So the comparison process animation shows

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;
    }
    
    // Let the first half and the second half compare
    bool chkPalindrome(ListNode* A) {
    
        struct ListNode* head = A;
        struct ListNode* mid = middleNode(head); //找到中间节点
        struct ListNode* newHead = reverseList(mid); //Invert from the middle node,And give the result of the inversionnewhead
        while (newHead) {
    
            if (head->val != newHead->val) {
     //如果原节点的val 不等于 新节点的val
                return false; //返回
            }
            else {
    
                head = head->next;
                newHead = newHead->next;
            }
        }
        return true;
    }
};

提交结果