前言
本系列主要讲解链表的经典题
注：划重点！！必考~
链表分割
牛客链接：链表的回文结构_牛客题霸_牛客网 (nowcoder.com)
题目描述：
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
解题思路：
- 这里我们先找到中间结点（使用快慢指针法）
- 快指针每次走两个结点的位置，慢指针每次走一个结点的位置
- 快指针走到结束位置时，慢指针恰到中间位置
- 从中间结点开始对接下来每个结点进行改变结点方向
- 最后对两个头结点开始逐个遍历接下来的结点，直到相遇
图示：
参考代码：
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class PalindromeList { public: bool chkPalindrome(ListNode* A) { //快慢指针找到中间结点 struct ListNode*fast=A,*slow=A; while(fast&&fast->next) { fast=fast->next->next; slow=slow->next; } struct ListNode*cur=slow; //两个指针用来逆转节点方向 struct ListNode*prev=NULL,*next; while(cur) { struct ListNode*Next=cur->next; cur->next=prev; prev=cur; cur=Next; } //遍历比较 struct ListNode*cur1=A,*cur2=prev; while(cur1&&cur2) { if(cur1->val==cur2->val) { cur1=cur1->next; cur2=cur2->next; } else return false; } return true; } };
结果：
