1. 题目介绍
链接: link
这道题呢是让我们判断一个链表是否是回文结构。但是题目要求设计一个时间复杂度为O(n)
,额外空间复杂度为O(1)
的算法。
所以如果我们想把链表的值存到一个数组中再去判断就不可行了。
2. 思路分析
那对于这道题呢比较好的一个思路是这样的:
不是要判断链表是否是回文结构嘛。
回文结构的话就是从中间分开,两边是对称的嘛(比如:1,2 | 2,1
),当然如果是奇数个结点的话就是以中间结点为对称轴(比如:1 2 3 2 1)。
那我就可以这样做:
找到链表的中间结点,将从中间结点开始往后的部分进行逆置(如果是偶数个有两个中间结点就从第二个开始)。
后半部分逆置之后,我们比较这两部分是否相同,如果相同,他就是回文结构。
单凭上面的文字大家可能还不是特别清楚,下面我们来画个图分析一下:
就以1 2 2 1为例:
首先找到中间结点是2(第二个2),这里找链表中间结点我们前面就做过这个题,到时候就可以直接用。
那逆置之后就是这样
链表逆置之前我们也写过对应的OJ题,待会也可以直接用。那逆置之后我们可以拿到逆置之后后半部分链表的头指针。
同时题目给了我们原链表的头指针。
那然后我们就可以同时从这两个头指针开始往后遍历,依次两个比较每对结点,如果某次比较不相同,那就不是回文结构,直接返回false。
如果是回文结构,就一直向后比,所以肯定要写成循环,那循环什么时候结束呢?
🆗,后半部分链表逆置之后最后一个结点指向空,所以如果遍历到rhead
为空,还没返回false,那就是全部相同,他就是回文结构,此时循环结束,返回true。
但是上面我们分析的是偶数个结点的情况,如果是奇数个,还适用吗?
🆗,是可以的。
以1 2 3 2 1为例
逆置后半部分之后是这样子。
然后还是两两比较,1 2相等,2 2 相等
此时我们看到对于前半部分链表来说,到2就遍历完了。后半部分虽然每遍历完,但是奇数个的话,他最后剩下的那个就是原链表最中间的那个结点。
那中间结点的左右两部分都相等了,其实已经证明是回文了,就可以结束了。
所以逆置之后是不是应该把前半部分的尾结点next置空,这样只要有一个链表走到空就结束,就是回文。
可以置空,但是其实没必要。而且要置空的话还得保存一下中间结点的前一个,怪麻烦的。
我们看到,不置空的话,此时前半部分的尾结点(这里是2)指向谁?
就是原链表的中间结点,所以可以继续向后比较,自己跟自己比,肯定相同,那再往后后半部分链表就走到空了。循环结束,返回true。
如果不是回文链表,中间比较的时候不相同就直接返回false了。
所以不需要将前半部分尾结点next置空,循环结束的条件就是后半部分链表走到空。
3. 代码实现
那我们来写一下代码:
这两个函数我就直接拷贝之前我们写过的代码了,之前的文章我们都讲过,大家可以去看。
就搞定辽!
提交一下:
过啦!
class PalindromeList {
public:
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* newhead = NULL;
struct ListNode* cur = head;
struct ListNode* tmp = NULL;
while (cur) {
//保存下一个的地址
tmp = cur->next;
//头插
cur->next = newhead;
newhead = cur;
cur = tmp;
}
return newhead;
}
struct ListNode* middleNode(struct ListNode* head) {
struct ListNode* slow = head;
struct ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
bool chkPalindrome(struct ListNode* A) {
struct ListNode* midnode=middleNode(A);
struct ListNode* rhead=reverseList(midnode);
while(rhead)
{
if(A->val!=rhead->val)
return false;
A=A->next;
rhead=rhead->next;
}
return true;
}
};