Palindrome Linked List

In this article, we will explore different approaches to check if the given linked list is a palindrome or not.

Problem Statement:

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

Approach 1: Use Extra Array

1. Traverse the linked list and copy each element into an array.

2. Use two pointers, one starting from the beginning of the array and the other from the end, and compare the values at each position.

3. Move the pointers towards the centre until they meet or cross each other.

4. If all the values match until the pointers meet, then the linked list is a palindrome. Otherwise, it is not.

// ES6 Arrow Function
const isPalindrome = head => {
    let arr = [];

    // Copy the list values to array
    while(head !== null) {
        arr.push(head.val);
        head = head.next;
    }

    let left = 0, right = arr.length - 1;

    while(left < right) {
        if(arr[left] !== arr[right]) return false;
        left++;
        right--;
    }

    return true;
}

Time Complexity: O(N)

Copying the linked list values to an array requires traversing the linked list once, which takes O(N) time and then the array elements from both ends take linear time as well. Therefore the time complexity is linear.

Space Complexity: O(N)

We are creating an array of size N, where N is the number of nodes in the linked list. Therefore the space complexity is linear.

Approach 2: Stack

The idea is that by using a stack, the code stores the values of the linked list in reverse order. Then, it compares these reversed values with the original values by traversing the linked list again. If all the values match, the linked list is a palindrome.

1. Create a pointer that starts at the head of the linked list and will be used to traverse the list. Create an empty stack as well to store all the elements of the linked list in reverse order.

2. Push the elements of the linked list to the stack. This process effectively stores the values of the linked list in reverse order within the stack.

3. Check for the palindrome, and loop through the linked list using the pointer we created. In each iteration, we compare the value of the current node with the value popped from the stack.

4. If the values are not equal then it’s not a palindrome, so it returns false. Otherwise, returns true.

// ES6 Arrow Function
const isPalindrome = head => {
    let newHead = head;
    let stack = [];

 // push the elements to the stack
    while(head) {
        stack.push(head.val);
        head = head.next;
    }

 // check if every list element is equal to value popped from stack(it is reverse of link list)
    while(newHead){
        if(newHead.val != stack.pop())
            return false;
        newHead = newHead.next;
    }

    return true;
};

Time Complexity: O(N)

The first while loop iterates over the linked list and pushes each node’s value onto the stack. This loop has a time complexity of O(n), where n is the number of nodes in the linked list. The second while loop iterates over the linked list again to compare each node’s value with the value popped from the stack. This loop also has a time complexity of O(n). Therefore, the overall time complexity of the code is linear.

Space Complexity: O(N)

The space complexity is determined by the additional memory used by the stack. The stack size depends on the number of nodes in the linked list. In the worst case, where all the elements in the linked list are unique, the stack will store n elements, resulting in a space complexity of O(n). Therefore, the overall space complexity is constant.

Approach 3: Reverse The Second Half

1. Traverse the linked list to find its middle point. We will use the slow and fast pointer technique, where the slow pointer moves one step at a time while the fast pointer moves two steps at a time. When the fast pointer reaches the end of the list, the slow pointer will be at the middle point.

2. Reverse the second half of the linked list starting from the node pointed to by the slow pointer.

3. Compare the values of nodes in the first half (from the head to the node before the slow pointer) with the reversed second half (from the slow pointer to the end).

4. If all the values match, then the linked list is a palindrome. Otherwise, it is not.

// ES6 Arrow Function
const isPalindrome = head => {
    // Find the middle of the linked list
    let slow = head;
    let fast = head;

    while(fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // Reverse the second half of the list
    let secondHalf = reversedLinkedList(slow);

    // Compare the first half with the reversed second half
    while(secondHalf !== null) {
        if(head.val !== secondHalf.val) return false;
        head = head.next;
        secondHalf = secondHalf.next;
    }

    return true;
}

// Helper function to reverse the linked list
const reversedLinkedList = head => {
    let prev = null;
    let curr = head;

    while(curr !== null) {
        let next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }

    return prev;
}

Time Complexity: O(N)

Firstly we are finding the middle of the linked list using fast and slow pointers which takes O(N/2) time. Then we are reversing the second half of the linked list which again takes O(N/2) time. Now, comparing the first and second half takes O(N/2) time as well. Therefore, the overall time complexity is linear.

Space Complexity: O(1)

We are not using any additional space throughout the algorithm. Therefore, the space complexity is constant.

Why does comparing the linked list with its reverse will not work?

I can sense that when you read the problem description, a thought may have crossed your mind — “Why not just reverse the linked list and compare it to the original? If they match, it’s a palindrome, right?”

It’s a tempting idea, and I admit, I had the same idea when I first saw the question. Well, I have to shatter your hopes and explain why this approach is flawed.

The “Reverse and Compare” technique fails because it only checks for the palindromic property of the linked list (i.e., having the same elements in reverse order) without considering the correct ordering of elements.

Therefore, it’s crucial to use other approaches, such as reversing the second half or using fast and slow pointers, that consider both value equality and the correct ordering of elements to determine if a linked list is a palindrome.

Let’s understand this with an example-

Consider the linked list: 1 -> 2 -> 3 -> 2 -> 1

To determine if this linked list is a palindrome, the “Reverse and Compare” technique suggests reversing the entire linked list and comparing it with the original list.

1. Reverse the linked list: Reversed list: 1 <- 2 <- 3 <- 2 <- 1

2. Compare the reversed list with the original list:

Original list: 1 -> 2 -> 3 -> 2 -> 1

Reversed list: 1 <- 2 <- 3 <- 2 <- 1

Comparing the reversed list with the original list element by element, we see that they match perfectly. Hence, one might assume that the linked list is a palindrome. However, this approach is flawed.

Let’s consider another example: 1 -> 2 -> 3 -> 2 -> 2

1. Reverse the linked list: 2 <- 2 <- 3 <- 2 <- 1

2. Compare the reversed list with the original list:

Original list: 1 -> 2 -> 3 -> 2 -> 2

Reversed list: 2 <- 2 <- 3 <- 2 <- 1

By comparing the reversed list with the original list, the technique falsely suggests that the linked list is a palindrome. However, in reality, the linked list is not a palindrome since the ordering of elements is different.

To correctly determine if a linked list is a palindrome, it is essential to consider the ordering of elements.

And there you have it guys! We’ve explored two different approaches, saw why the reverse and compare approach will not work, and hopefully had some fun along the way. I hope this article has provided you with valuable insights and helped you better understand the different approaches to solving this problem. Happy coding!

Problem - Leetcode 234