Two Algorithms to Determine a Palindrome Linked List using a Stack

Given a singly linked list node whose values are integers, determine whether the linked list forms a palindrome. A palindrome is defined as a sequence whose values are the same read forward and backwards.
For example, 5 -> 3 -> 5 is a palindrome, whereas 5 -> 3 -> 6 is not.

Constraints
n ≤ 100,000 where n is the length of node
Example 1
Input
node = 5 → 3 → 5
Output
true
Explanation
5 – 3 – 5 is a palindrome.

Example 2
Input
node = 12 → 8 → 12
Output
true
Explanation
The values of the linked list are the same forwards and backwards.

Using a Stack to Determine if a Linked List is a Palindrome

We can use a stack and push all the nodes in the linked list to it. Then by popping each node we are actually reversing the linked list – we just have to check if it match the node sequence from the begining.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/**
 * class LLNode {
 *     public:
 *         int val;
 *         LLNode *next;
 * };
 */
bool isPalindromeLinkedList(LLNode* node) {
    if (!node) return true;
    stack<LLNode*> st;
    LLNode* head = node;
    while (head) {
        st.push(head);
        head = head->next;
    }
    while (!st.empty()) {
        auto p = st.top();
        st.pop();
        if (p->val != node->val) return false;
        node = node->next;
    }
    return true;
}

/**
 * class LLNode {
 *     public:
 *         int val;
 *         LLNode *next;
 * };
 */
bool isPalindromeLinkedList(LLNode* node) {
    if (!node) return true;
    stack<LLNode*> st;
    LLNode* head = node;
    while (head) {
        st.push(head);
        head = head->next;
    }
    while (!st.empty()) {
        auto p = st.top();
        st.pop();
        if (p->val != node->val) return false;
        node = node->next;
    }
    return true;
}

The time complexity is O(N) where N is the number of the nodes in the linked list – but we are traversing the linked list three times. The space complexity is O(N) as we are using a stack to store the nodes in the linked list.

We need only store half of the linked list. We can do this by using a fast/slow pointer where the fast pointer moves 2 steps and the slow pointer moves 1 step at a time. When the fast pointer reaches the end of the linked list, the slow pointer is at the middle. Thus from the middle, we can push all the nodes till the end to the stack, and then compare backwards (as the stack pops) to the nodes that are visited from the begining. This way, we only need O(N/2) space (which is O(N)), and the time complexity is still O(N) but we only need to visit the linked list twice.

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

/**
 * class LLNode {
 *     public:
 *         int val;
 *         LLNode *next;
 * };
 */
bool isPalindromeLinkedList(LLNode* node) {
    if (!node) return true;
    stack<LLNode*> st;
    LLNode* fast = node;
    LLNode* slow = node;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    LLNode* head = slow;
    while (head) {
        st.push(head);
        head = head->next;
    }
    while (!st.empty()) {
        auto p = st.top();
        st.pop();
        if (p->val != node->val) return false;
        node = node->next;
    }
    return true;
}

/**
 * class LLNode {
 *     public:
 *         int val;
 *         LLNode *next;
 * };
 */
bool isPalindromeLinkedList(LLNode* node) {
    if (!node) return true;
    stack<LLNode*> st;
    LLNode* fast = node;
    LLNode* slow = node;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    LLNode* head = slow;
    while (head) {
        st.push(head);
        head = head->next;
    }
    while (!st.empty()) {
        auto p = st.top();
        st.pop();
        if (p->val != node->val) return false;
        node = node->next;
    }
    return true;
}

To determine if a linked list is palindrome, we have to reach/visit the end of the linked list and then pop the elements from the stack. If it is a double-linked list we can just move to the end and then compare the node values at both ends while they move towards the middle. If the head node connects to tail, it would be even simpler.

–EOF (The Ultimate Computing & Technology Blog) —