前言
本系列主要讲解链表的经典题 注:划重点!!必考~
链表分割
对于一个链表,请设计一个时间复杂度为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;
}
};
每日k题无烦恼,点赞学习不得了~