LeetCode热题100 回文链表

题目描述

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入： head = [1,2,2,1]
输出： true

示例 2：

输入： head = [1,2]
输出： false

提示：

$链表中节点数目在范围[1,10^5]内$
$0<=Node.val<=9$

思路

1 使用快慢指针获取中心位置。
2 将其中一部分进行翻转后进行一一对比。

代码

class Solution {
public:
bool isPalindrome(ListNode* head) {
if(head == nullptr || head->next == nullptr) return true;

// 1 获取第一部分尾部
ListNode *firstHalfEnd = endOfFirstHalf(head);
// 2 将第二部分进行翻转
ListNode *secondHalfStart = reverseList(firstHalfEnd->next);
// 3 对比是否相等
ListNode *p1 = head;
ListNode *p2 = secondHalfStart;
bool res = true;
while(p2 != nullptr)
{
if(p1->val != p2->val)
{
res = false;
break;
}
p1 = p1->next;
p2 = p2->next;
}
// 4 翻转回去复原
firstHalfEnd->next = reverseList(secondHalfStart);
return res;
}
// 快慢指针获取中间部分 (n+1)/2
ListNode *endOfFirstHalf(ListNode *head)
{
ListNode *fast = head;
ListNode *slow = head;
while(fast->next != nullptr && fast->next->next != nullptr)
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
// 对链表进行翻转
ListNode* reverseList(ListNode* head)
{
ListNode * tail = nullptr;
ListNode * cur = nullptr;
while(head != nullptr)
{
// 保存下一个位置
ListNode * cur = head->next;
// 修改当前位置的指向
head->next = tail;
tail = head;
// 获取下一个位置
head = cur;
}
return tail;
}
};