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

Flatten Binary Tree To Linked List Problem

LeetCode 114. Given the root of a binary tree, flatten...

Remove Duplicates from Sorted List Problem

LeetCode 83. Given the head of a sorted linked list,...

Rotate List Problem

LeetCode 61. Given the head of a linked list, rotate...

Reverse Nodes in k-Group Problem

LeetCode 25. Given a linked list, reverse the nodes of...

Swap Nodes in Pairs Problem

LeetCode 24. Given a linked list, swap every two adjacent...