0%

[Leetcode]234. Palindrome Linked List(C++)

题目描述

题目链接: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?

解题思路

题目要求判断链表是否回文(顺着读和反着读顺序数字一样),并且要求线性时间和常数空间内完成。我们可以首先计算出链表的长度,然后从中间断开链表,(如果是奇数个节点不考虑中间那个节点),再将后半段链表反转一下,最后依次比较两半链表即可。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 * 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