给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。 输入:head = [1,2,2,1] 输出:true…
- User
给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。
输入:head = [1,2,2,1] 输出:true
输入:head = [1,2] 输出:false
请补充这一段代码: class Solution { public: bool isPalindrome(ListNode* head) { }}
Assistant
我会提供一个高效的解决方案,并详细解释实现思路。这里我们使用快慢指针找中点,然后反转后半部分链表,最后比较前后两部分。
class Solution { public: bool isPalindrome(ListNode* head) { if (head == nullptr || head->next == nullptr) return true; // 1. 找中点 ListNode* slow = head; ListNode* fast = head; while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; } // 2. 反转后半部分链表 ListNode* secondHalf = reverseList(slow->next); // 3. 比较前后两部分 ListNode* firstHalf = head; while (secondHalf) { if (firstHalf->val != secondHalf->val) return false; firstHalf = firstHalf->next; secondHalf = secondHalf->next; } return true; } private: // 反转链表的辅助函数 ListNode* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* curr = head; while (curr) { ListNode* nextTemp = curr->next; curr->next = prev; prev = curr; curr = nextTemp; } return prev; } };这个解决方案的时间复杂度是 O(n),空间复杂度是 O(1)。
解题步骤:
-
特殊情况处理:
- 如果链表为空或只有一个节点,直接返回 true
-
找中点:
- 使用快慢指针
- 快指针每次走两步,慢指针每次走一步
- 当快指针到达末尾时,慢指针恰好在中间
-
反转后半部分链表:
- 从中点后一个节点开始反转链表
- 使用 reverseList 辅助函数实现
-
比较前后两部分:
- 从头节点和反转后的后半部分同时开始比较
- 如果值不同,返回 false
- 比较完成,返回 true
示例:
-
输入 [1,2,2,1]
- 找中点后:[1,2] | [2,1]
- 反转后半部分:[1,2] | [1,2]
- 比较相等,返回 true
-
输入 [1,2]
- 找中点后:[1] | [2]
- 反转后半部分:[1] | [2]
- 比较不相等,返回 false
这个方法既高效又不需要额外的空间,是解决回文链表问题的最优解。
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.