链表的回文结构(C++超详细讲解)
C++实现判断链表的回文结构
- 思路
- 代码实现
题目描述
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：
1->2->2->1
返回：true
思路
判断链表的回文结构，采取快慢指针的方法，即快指针一次走两步，慢指针一次走一步
可将链表分为两种情况
- 链表含有偶数个节点
首先通过慢指针找到中间节点，如下图所示，当fast==NULL时停止
将中间指针后面的节点逆置最后两个指针一个从左向右一个从右向左，当pleft->next==pright时结束
- 链表含有奇数个节点的情况
首先通过慢指针找到中间节点，当fast->next==NULL时结束
然后逆置中间节点后的节点
最后两个指针一个从左向右一个从右向左，当plef==pright时结束
代码实现
/*struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}};*/class PalindromeList {public:bool chkPalindrome(ListNode* A) {//1、链表为空或者只有一个节点则返回trueif(A==NULL || A->next==NULL)return true;//2.链表多于一个节点ListNode * pfast = A; //快指针ListNode * pslow = A; //慢指针//偶数个节点时fast==NULL结束，奇数个节点时fast->next==NULL结束//while循环的条件是继续的条件，而我们思考的是while停止的条件，因此条件是反过来的while(!(pfast == NULL || pfast->next == NULL)){pfast = pfast->next->next; //快指针一次走两步pslow = pslow->next; //慢指针一次走一步}//逆置节点,采用头插法,每次从链表中取出一个节点插入到pre节点之前ListNode * prev = pslow;pslow = pslow->next;prev->next = NULL; //中间节点置空while(pslow!=NULL){ListNode * tmp =pslow->next; //保存当前节点的后一个节点防止丢失pslow->next=prev; //当前节点指向前一个节点prev=pslow; //prev和pslow分别后移pslow=tmp;}ListNode * pleft = A; //指向头节点ListNode * pright = prev; //指向尾节点while(!(pleft==pright || pleft->next == pright)){if(pleft->val != pright->val)return false;else{pleft = pleft->next;pright = pright->next;}}return true;}};
ゝ一纸荒年。
深藏阁楼爱情的钟
系统管理员
你的名字
我会带着你远行
还没有评论，来说两句吧...