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 front;
public boolean isPalindrome(ListNode head) {
    front = head;
    return solve(head);
}

private boolean solve(ListNode head){
    if(null == head){
        return true;
    }    
    // on the way back, compare the elements from the beginning of the list
    boolean matchedSoFar = solve(head.next) && head.val == front.val;
    if(matchedSoFar){
        front = front.next;
    }
    return matchedSoFar;
}

The above implementation uses a recursive approach to solve the problem. The front 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 front 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.

Step 1: Traversal to End (Recursive Calls)
-------------------------------------------
head → [1] → [2] → [2] → [1] → null
front → [1]

After reaching null, start unwinding the recursion.

Step 2: Backtracking and Comparing
-----------------------------------
[1] ← [2] ← [2] ← [1]  (Returning up the recursion stack)

Comparisons (in backtracking):
front = 1   | back = 1 ✅  (Move front to next)
front = 2   | back = 2 ✅  (Move front to next)
front = 2   | back = 2 ✅  (Move front to next)
front = 1   | back = 1 ✅  (Move front to next)

Result: true

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.