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;
}




Related Posts

Add Two Numbers Problem

LeetCode 2. You are given two non-empty linked lists representing...

Reverse Linked List Problem

LeetCode 206. Reverse a singly linked list.

Reverse Linked List II Problem

LeetCode 92. Reverse a linked list from position m to...

Palindrome Linked List Problem

LeetCode 234. Given a singly linked list, determine if it’s...

Merge K Sorted Lists Problem

LeetCode 23. You are given an array of k linked-lists...

Merge Two Sorted Lists Problem

LeetCode 21. Merge two sorted linked lists and return a...