题目描述:
对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。
测试样例:
1->2->2->1
返回:true
代码格式:
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
bool chkPalindrome(ListNode* A)
{
//write code here
}
};
本题解法分析:
回文结构,就是从前往后读和从后往前读相同,也就是前半部分和后半部分的逆序相同,那么我们以此为出发点,先把链表分割成两部分,再对后半部分进行逆序,最后进行比较不就好了吗?
- 首先找到中间结点
- 将中间结点后半部分倒置
- 分别从头结点和尾结点向中间遍历,检测在达到中间时刻之间val的值是否都相等
1.找中间节点:我们用快慢指针发法找中间节点,也就是快指针走两步,慢指针走一步,当快指针走到头(即其下一个节点为NULL)的时候,那么此时慢指针也就刚好走到中间。
ListNode* findmidnode(ListNode* A)//快慢指针法
{
ListNode* phead=(ListNode*)malloc(sizeof(ListNode));//头哨兵
phead->next=A;
ListNode* fast=phead;
ListNode* slow = phead;
while(fast)
{
slow=slow->next;
if(fast->next)
{
fast=fast->next->next;
}
else
{
return slow;
}
}
return slow;
}
2.反转后半部分链表 :我们首先要记录当前节点cur的下一个节点tmp(以便当前节点被更新后找不到下一个节点),然后使当前节点的next指向前面的prev(初值为NULL,因为结束时头要当尾),再然后使prev=cur,cur=tmp。这样就构成了循环,实现了反转;
ListNode* Listreverse(ListNode* mid)
{
ListNode* prev = NULL;
ListNode* cur = mid;
while(cur)
{
ListNode* tmp = cur->next;
cur->next=prev;
prev=cur;
cur=tmp;
}
return prev;
}
结合起来就是本题的答案:
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
ListNode* findmidnode(ListNode* A)
{
ListNode* phead=(ListNode*)malloc(sizeof(ListNode));//头哨兵
phead->next=A;
ListNode* fast=phead;
ListNode* slow = phead;
while(fast)
{
slow=slow->next;
if(fast->next)
{
fast=fast->next->next;
}
else
{
return slow;
}
}
return slow;
}
ListNode* Listreverse(ListNode* mid)
{
ListNode* prev = NULL;
ListNode* cur = mid;
while(cur)
{
ListNode* tmp = cur->next;
cur->next=prev;
prev=cur;
cur=tmp;
}
return prev;
}
class PalindromeList {
public:
bool chkPalindrome(ListNode* A)
{
//找到中间节点
ListNode* mid = findmidnode(A);
//反转后半段
ListNode* reverse = Listreverse(mid);
while(reverse)//因为reverse的尾部为NULL,而A要比reverse长,我们只判断A的前一半
{
if(reverse->val!=A->val)
{
return false;
}
reverse=reverse->next;
A=A->next;
}
return true;
}
};