闯关leetcode——234. Palindrome Linked List

题目

地址

https://leetcode.com/problems/palindrome-linked-list/description/

内容

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

Constraints:

• The number of nodes in the list is in the range [1, 105].
• 0 <= Node.val <= 9

Follow up: Could you do it in O(n) time and O(1) space?

解题

这题就是要检测一个链表是否符合回文结构。一种比较简单的思路就是使用栈来将链表内容反序，然后逐项对比。但是这个方案不符合O(1) space的要求，因为辅助计算的栈中数据大小会随着链表中数据量增大而增大。

回文数的结构是中间对称。虽然使用栈来处理可以避免对“中间”的寻找，但是O(1) space限制了我们对栈的使用。这就促使我们要来寻找“中间”。一种简单的办法就是使用不同速度的指针向后探寻——一个一次向后移动一个元素，一个一次向后移动两个元素。这样快的那个指针会先到链表末尾，而慢的那个指针则会找到“中间”附近的位置。

为什么是“中间”附近的位置呢？因为链表的元素数量可能是奇数，也可能是偶数。如下图所示，如果是奇数，慢指针将指向“中间”的前一个元素；如果是偶数，慢指针指向的是回文左半边的最后一个元素。

不管慢指针指向的是哪种情况，我们都已让其下一个元素（含）之后的所有元素反转，然后从链表头部开始对比。只要一个链表遍历结束后，仍然没有出现不同值的元素，则可以认为是回文数。

struct ListNode {int val;ListNode *next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {}
};class Solution {
public:bool isPalindrome(ListNode* head) {if (head == nullptr || head->next == nullptr) return true;ListNode* slow = head;ListNode* fast = head->next;while (fast != nullptr && fast->next != nullptr) {slow = slow->next;fast = fast->next->next;}ListNode* pre = nullptr;ListNode* cur = slow->next;slow->next = nullptr;while (cur != nullptr) {ListNode* next = cur->next;cur->next = pre;pre = cur;cur = next;}while (head != nullptr && pre != nullptr) {if (head->val != pre->val) return false;head = head->next;pre = pre->next;}return true;}
};

代码地址

https://github.com/f304646673/leetcode/blob/main/234-Palindrome-Linked-List/cplusplus/src/solution.hpp