题目描述
对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。
给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。(题目来源)
思路
我们需要找到传入链表的中间结点,并将中间结点及其后面结点进行反转,然后再将原链表的前半部分与反转后的后半部分进行比较,若相同,则该链表是回文结构,否则,不是回文结构。
1.找到链表的中间结点。
2.反转中间结点及其后面的结点。
3.比较链表的前半部分与后半部分的结点值,若相同则是回文结构,否则,不是回文结构。
将A指针指向的结点与RHead指针指向的结点进行比较,若相同,则两个指针后移,继续比较后面的结点,直到RHead指针指向NULL时,比较结束。
注意:就算传入的链表是结点数为奇数的回文结构,该思路也可以成功判断。
例如,以下链表反转其后半部分后,我们看似链表应该是这样的。
但反转后的链表并不是这样的,而应该是下面这样:
因为我们反转的是中间结点及其后面的结点,并没有对前面的结点进行任何操作,所以结点5所指向的结点应该还是结点7。
于是该链表的比较过程应该是这样的:1等于1,3等于3,5等于5,7等于7,然后RHead指针指向NULL。所以判断该链表是回文结构。
代码实现
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class PalindromeList {
public:
//查找链表的中间结点
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* fast = head;//快指针
struct ListNode* slow = head;//慢指针
while (fast&&fast->next)//遍历继续的条件
{
slow = slow->next;//慢指针一次走一步
fast = fast->next->next;//快指针一次走两步
}
return slow;//返回慢指针
}
//反转链表
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* cur = head;//记录当前待头插的结点
struct ListNode* newhead = NULL;//新链表初始时为空
while (cur)//链表中结点头插完毕时停止循环
{
struct ListNode* next = cur->next;//记录下一个待头插的结点
cur->next = newhead;//将结点头插至新链表
newhead = cur;//新链表头指针后移
cur = next;//指向下一个待头插的结点
}
return newhead;//返回反转后的头指针
}
bool chkPalindrome(ListNode* A) {
ListNode* mid = middleNode(A);//查找链表的中间结点
ListNode* RHead = reverseList(mid);//反转后半段链表
while (RHead)//比较结束的条件
{
if (A->val != RHead->val)//不是回文结构
return false;
A = A->next;//指针后移
RHead = RHead->next;//指针后移
}
return true;//是回文结构
}
};
注:链表的中间结点和反转链表的题目已经讲述过,在此就不再过多论述。