Palindrome Linked List

Checking Palindrome in a Singly Linked List using Stack

To determine whether a given singly linked list is a palindrome or not, we can utilize a stack. A palindrome linked list is one that reads the same from both ends, i.e., from head to tail and tail to head.

Here's an approach using a stack:

• Traverse the linked list from head to tail.
• Push the data property of each node into a stack.
• Reset the pointer to the head of the linked list.
• Traverse the linked list node by node and pop each element from the stack.
• If the data of the current node is not equal to the popped element from the stack, return false.
• If the stack becomes empty during the traversal, return true.

Here's an implementation of the algorithm in Java:

public boolean isPalindrome(ListNode head) {
    ListNode temp = head;
    Stack<Integer> stack = new Stack<>();

    // Step 1: Traverse the linked list and push data into the stack
    while (temp != null) {
        stack.push(temp.val);
        temp = temp.next;
    }

    temp = head; // Reset the pointer to the head

    // Step 4: Traverse the linked list and pop elements from the stack
    while (temp != null) {
        int poppedItem = stack.pop();

        // Step 5: Compare the data of the node with the popped element
        if (temp.val != poppedItem)
            return false;

        temp = temp.next;
    }

    // Step 6: If the stack is empty, it's a palindrome
    return stack.isEmpty();
}

Time Complexity

We traverse the linked list twice: once to push elements into the stack and again to compare them with the popped elements. Hence, the time complexity is O(n), where n is the size of the linked list.

Space Complexity

Using a stack to store all the nodes requires additional space. The space complexity is O(n), where n is the size of the stack.