Palindrome Linked List Problem
Description
LeetCode Problem 234. Given a singly linked list, determine if it is a palindrome.
Example:
1
2
3
4
5
Input: 1->2
Output: false
Input: 1->2->2->1
Output: true
Solution
A simple solution is to iterate through the list, store the node values to an array and check whether the array is palindrome. The time complexity of this approach is O(n), and the space complexity is also O(n).
We can reduce the space complexity to O(1), without increasing the time complexity. This solution requires modifying the list. The solution is similar to the reverse linked list problem.
We first iterate through the list, and count the number of nodes in the list.
Then we iterate through the list again. This time, if the current node is in the first half of the list, we reverse the list using the same approach as in the reverse linked list problem. We use a pointer prev to record the head of the reversed half of the list.
If the current node is in the second half of the list, we compare the current node with the prev node to check whether the list is palindrome. If the value of the prev node and the current node does not match, we return false. We repeat it until we reach the end of the list. Note that the prev node goes from the middle of the list to the beginning of the list, and the current node goes from the middle of the list to the end of the list. When we reach the end of the list and all node values match, we return true.
The time complexity of this approach is O(n), and the space complexity is O(1).
Sample C++ Code
This is a C++ implementation of the above approach.
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
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <algorithm>
using namespace std;
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) {}
};
bool isPalindrome(ListNode* head) {
ListNode* curr = head;
ListNode* prev = head;
ListNode* tmp;
if ((head == NULL) || (head->next == NULL))
return true;
int cnt = 0;
while (curr != NULL) {
cnt ++;
curr = curr->next;
}
curr = prev->next;
int i = 1;
prev->next = NULL;
while (curr != NULL) {
if ((cnt % 2 == 1) && (i == cnt / 2)) {
curr = curr->next;
} else if (i < cnt / 2) {
tmp = curr;
curr = curr->next;
tmp->next = prev;
prev = tmp;
} else {
if (curr->val != prev->val) {
return false;
}
curr = curr->next;
prev = prev->next;
}
i ++;
}
return true;
}
int main() {
ListNode* lhead = new ListNode(1);
ListNode* curr = lhead;
curr->next = new ListNode(2);
curr = curr->next;
curr->next = new ListNode(3);
curr = curr->next;
curr->next = new ListNode(2);
curr = curr->next;
curr->next = new ListNode(1);
cout << isPalindrome(lhead) << endl;
return 0;
}