目录
一、描述
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：
1->2->2->1
返回：true
二、思路
顾名思义，检查两端是否对称。
但是：单链表不具有双向箭头，所以只能逆置链表。
1->2->2->1
逆置后半部分2->1
逆置成1->2
则1->2->2->1变成1->2->1->2
找到链表的中间节点，便可以进行比较。
三、链表的逆置
题目：反转链表-CSDN博客（保姆级教学）
四、代码的实现
bool chkPalindrome(ListNode* A) {
// write code here
ListNode* cur = A;
if(A == NULL || A->next == NULL)
return true;
int count = 0;
while(cur)
{
cur = cur->next;
count++;
}
cur = A;
ListNode* prev = NULL;
while(count > 0) //让cur指向需要逆置字符串的首节点。
{
prev = cur;
cur = cur->next;
count -= 2;
}
ListNode* newhead = NULL, *next = NULL;
next = cur->next;
while(cur)
{
cur->next = newhead;
newhead = cur;
cur = next; //cur不断往下进行
// cur = cur->next;
if(next)
next = next->next;
}
prev->next = newhead;
cur = A;
int flag = 1;
while(newhead)
{
if(cur->val != newhead->val)
{
flag = 0;
break;
}
cur = cur->next;
newhead = newhead->next;
}
if(flag == 1)
return true;
else
return false;
}五、代码解读
1.寻找中间节点
while(count > 0) //让cur指向需要逆置字符串的首节点。
{
prev = cur;
cur = cur->next;
count -= 2;
}
2.进行字符串的逆置
while(cur)
{
cur->next = newhead;
newhead = cur;
cur = next; //cur不断往下进行
// cur = cur->next;
if(next)
next = next->next;
}
3.判断
while(newhead)
{
if(cur->val != newhead->val)
{
flag = 0;
break;
}
cur = cur->next;
newhead = newhead->next;
}
六、注意点
进行链表的逆置的时候，需要借助next 、 和 cur 指针。
cur = next; //cur不断往下进行
// cur = cur->next;
当next不断往下遍历的时候， cur = next语句使cur不断往下进行。
// cur = cur->next; 这是一种错误的写法。（上一个语句中cur->next已经指向了newhead）
七、代码思路的优化
链表1：1 2 2 1
链表2：1 2 3 2 1
当两个链表的元素个数分奇偶，可以统一利用快慢指针找到中间节点再逆置
快慢指针：快慢指针：妙解查找链表的中间结点问题-CSDN博客
struct ListNode* middleNode(struct ListNode* head) {
struct ListNode* fast = head;
struct ListNode* slow = head;
while(fast){
if(fast->next){
fast = fast->next->next;
slow = slow->next;
}
else
fast = fast->next;
}
return slow;
}对于奇数个数的链表而言
mid指针会指向 3 这个元素
此时逆置结束后为1 2 1 2 3
此时比较时为1 VS1 , 2 VS 2 , 3 VS 3 （3 VS 3 是因为将3 2 1这三个节点逆置之后，前半部分的 第二个节点“ 2 ” ，仍然指向原来的第三个 节点3）。
