企业官网建设流程全解析

02.06、[简单] 回文链表

1、题目描述

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

2、解题思路：

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

3、代码实现与详细注释

class Solution { public: bool isPalindrome(ListNode* head) { // 如果链表为空或只有一个节点，直接返回 true if (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) { // 如果值不相等，返回 false return false; } slow = slow->next; // 两个指针同时移动 newhead = newhead->next; } // 如果链表前后部分相同，则返回 true return true; } };

4、时间复杂度和空间复杂度：

• 时间复杂度：O(n)，其中 n 是链表的长度。我们遍历链表两次，一次是找到中点，另一次是进行比较。
• 空间复杂度：O(1)，因为只使用了常数额外空间。

这个方法通过快慢指针和链表反转的技巧，避免了额外的空间开销，是一个比较高效的解决方案。