当前位置：首页 > news >正文

02.06、回文链表

news 2024/11/13 15:10:29

02.06、[简单] 回文链表

1、题目描述

编写一个函数，检查输入的链表是否是回文的。

2、解题思路：

快慢指针找中点：
- 利用快慢指针的技巧来找到链表的中间节点。慢指针 slow 每次移动一步，而快指针 fast 每次移动两步。这样，当快指针到达链表末尾时，慢指针恰好位于链表中间。
反转后半部分链表：
- 在找到中间节点后，将链表的后半部分反转。我们从 slow->next 开始反转链表，最终 newhead 将指向反转后的后半部分链表的头节点。
对比前半部分和后半部分：
- 反转链表的后半部分后，将它与前半部分进行比较。如果所有节点值相等，则说明链表是回文的。
返回结果：
- 如果比较过程中发现不一致，则返回 false。如果全部节点相等，则返回 true。

3、代码实现与详细注释

class Solution {
public:bool isPalindrome(ListNode* head) {// 如果链表为空或只有一个节点，直接返回 trueif (head == nullptr || head->next == nullptr) {return true;}// 使用快慢指针找到链表的中间节点ListNode* fast = head;ListNode* slow = head;while (fast->next && fast->next->next) {slow = slow->next;  // 慢指针每次移动一步fast = fast->next->next;  // 快指针每次移动两步}// 将链表的后半部分反转ListNode* newhead = slow->next;  // newhead 指向后半部分的开始节点ListNode* prev = nullptr;  // 用于反转链表while (newhead->next) {ListNode* next = newhead->next;  // 保存下一个节点newhead->next = prev;  // 当前节点的 next 指向前一个节点prev = newhead;  // prev 指向当前节点，逐步推进newhead = next;  // newhead 移动到下一个节点}newhead->next = prev;  // 最后一个节点反转后，形成新的链表// 对比前半部分和反转后的后半部分是否相同slow = head;  // slow 回到链表头部while (newhead) {  // 遍历反转后的链表if (newhead->val != slow->val) {  // 如果值不相等，返回 falsereturn false;}slow = slow->next;  // 两个指针同时移动newhead = newhead->next;}// 如果链表前后部分相同，则返回 truereturn true;}
};