数据结构-链表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;
}

以上为此篇全部内容！