题目描述
题目链接:234. Palindrome Linked List
Given a singly linked list, determine if it is a palindrome.
例子
例子 1
Input:
1->2
Output:false
例子 2
Input:
1->2->2->1
Output:true
Follow Up
- Could you do it in O(n) time and O(1) space?
解题思路
题目要求判断链表是否回文(顺着读和反着读顺序数字一样),并且要求线性时间和常数空间内完成。我们可以首先计算出链表的长度,然后从中间断开链表,(如果是奇数个节点不考虑中间那个节点),再将后半段链表反转一下,最后依次比较两半链表即可。代码如下:
* Definition for singly-linked list.
* 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) {
// compute the length of linked list
int n = 0;
ListNode *curr = head;
while(curr) {
curr = curr->next;
n++;
}
if (n <= 1) return true;
// move curr to the second half of linked list
curr = head;
for (int i = 0; i < n / 2; i++) {
curr = curr->next;
}
if (n % 2) {
curr = curr->next;
}
// reverse the second half of linked list
ListNode *prev = nullptr;
ListNode *next = curr->next;
curr->next = prev;
while(next) {
prev = curr;
curr = next;
next = curr->next;
curr->next = prev;
}
// compare the first half & reversed second half
while(curr && head) {
if (curr->val != head->val) return false;
curr = curr->next;
head = head->next;
}
return true;
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(1)
GitHub 代码同步地址: 234.PalindromeLinkedList.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions