数据结构-链表OJ-回文链表，如何将时间复杂度控制为O(N),空间复杂度控制为O(1)？

前言

本篇讲解链表的回文结构

回文链表

题目链接：https://leetcode.cn/problems/palindrome-linked-list/description/

我们仅讲解能够将时间复杂度控制为O(n) 并且将空间复杂度控制为 O(1)的思路

首先，题目要求我们判断是否为回文结构，那么我们可以和之前一样，以中间结点为切入点

我们采用快慢指针法，找到中间结点（当快指针为空或快指针的下一个结点为空时，慢指针刚好走到中间结点，如果有偶数个结点，那么记慢指针走到第三个结点为中间结点），之后对中间结点开始及之后的结点进行逆置，中间结点的前一个结点next置为空，逆置完成后，一个从新的头结点开始，另一个从头结点开始（中间结点之前的原头结点）开始进行比较，直到一方为空

实现代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool isPalindrome(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    struct ListNode* prev = slow;
    while(fast && fast->next)
    {
        prev = slow;
        slow = slow->next;
        fast = fast->next->next;
    }
    prev->next = NULL;
    struct ListNode* mid = slow;
    struct ListNode* prev1 = NULL;
    struct ListNode* next1 = mid;
    struct ListNode* cur = NULL;
    while(next1)
    {
        if(prev1 == NULL)
        {
            cur = prev1 = next1;
            next1 = next1->next;
            prev1->next = NULL;
        }
        else
        {
            cur = next1;
            next1 = next1->next;
            cur->next = prev1;
            prev1 = cur;
        }
    }
    struct ListNode* newhead = head;
    while(newhead)
    {
        if(newhead->val != cur->val)
        {
            return false;
        }
        newhead = newhead->next;
        cur = cur->next;
    }
    return true;
}

以上为此篇全部内容！