Palindrome Linked List

Problem Statement

LeetCode 234: Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Consider the following examples:

Input: head = [1,2,2,1]
Output: true

In the example above, the method should return true because the linked list when iterated from either end is the same. But the same does not hold true for next example:

Input: head = [1,2]
Output: false

Approach

There are multiple ways to solve this problem. One of the ways is to reverse the linked list (recursively or iteratively) and compare the reversed linked list with the original linked list. If they are the same, then the linked list is a palindrome.

A Stack can also be used to solve this problem, which essentially mimics a reversed linked list. The linked list is iterated once to push all the elements into the stack. Then the linked list is iterated again to pop the elements from the stack and compare them with the linked list. If they are the same, then the linked list is a palindrome.

Another way to solve this problem is a combination of recursive and iterative approach. The linked list is iterated recursively until the end of the linked list is reached. Then the linked list is iterated iteratively from the head of the linked list. The elements are compared at each step. If they are the same, then the linked list is a palindrome.

Implementation

Here is the implementation of the approach described above. Let’s implement the recursive and iterative approach to solve this problem.

private ListNode first = null;

public boolean isPalindrome(ListNode head) {
    first = head;
    return solve(head);
}

private boolean solve(ListNode head){
    boolean prev = true;
    if(null != head.next){
        prev = solve(head.next);
    }
    // now head points to last node
    if(prev && (head.val == first.val)){
        first = first.next;
        return true;
    }else{
        return false;
    }
}

The above implementation uses a recursive approach to solve the problem. The first pointer is used to iterate the list from the beginning, where as due to recursion, (on its way back) the head is used to iterate the list from end.

At any stage, if the elements are not same, then the method returns false. If the elements are same, then the first pointer is moved to the next element and the method returns true. Due to recursion, the head pointer will now point to the second last element and the comparison will continue.

Not let’s implement the Stack approach as well to solve this problem.

public boolean isPalindrome(ListNode head) {
    Stack<Integer> stack = new Stack<>();
    ListNode itr = head;
    while(null != itr){
        stack.push(itr.val);
        itr = itr.next;
    }
    // reset itr to head
    itr = head;
    while(null != itr){
        if(itr.val != stack.pop()){
            return false;
        }
        itr = itr.next;
    }
    return true;
}

Complexity Analysis

• Time Complexity: The time complexity for both the approaches is $O(N)$ where $N$ is the number of elements in the linked list.
• Space Complexity: The space complexity is also $O(N)$ for both the approaches recursive or explicit Stack.