Palindrome Linked List

Problem Statement

We are provided with a linked list (singly linked list) and we need to check whether the provided linked list is a palindrome linked list or not.

Now, palindrome means any word or sequence that reads the same forwards as backward. For example mom is a palindrome as it reads the same forwards as backward.

Refer to the Example and Explanation sections for more details and the Approach section to understand how to check a palindrome Linked List.

Example

We are also provided with a few examples.

Example 1: The given (input) linked list is : 1 -> 2 -> 3 -> 2 -> 1.

Answer: The given linked list is a palindrome linked list.

Example 2: The given (input) linked list is : 5 -> 4 -> 3 -> 2 -> 5.

Answer: The given linked list is not a palindrome linked list.

Example Explanation

Before getting into the explanation of how to check a palindrome Linked List, let us first get a brief introduction about the linked lists.

A linked list is a sequential collection of data elements connected via links. The data element of a linked list is known as a node which contains two parts namely- the data part and the pointer. The data part contains the actual data and the pointer part contains a pointer that points to the next element of the linked list.

Now, let us focus on the first provided example. The given linked list is: 1 -> 2 -> 3 -> 2 -> 1.

In the example above, we can see that if we traverse the list from left to right (i.e. forward direction) then we would get 1, 2, 3, 2, 1. Similarly, if we traverse the list from right to left (i.e. backward direction) then we would again get 1, 2, 3, 2, 1. As both the forward and backward traversal results in the same sequence of values. So, the provided linked list is a palindrome linked list and we will return True.

In the second provided example, the given linked list is: 5 -> 4 -> 3 -> 2 -> 5.

In the example above, we can see that if we traverse the list from left to right (i.e. forward direction) then we would get 5, 4, 3, 2, 5. And if we traverse the list from right to left (i.e. backward direction) then we would again get 5, 2, 3, 4, 5. As both the forward and backward traversal results do not result in the same sequence of values. So, the provided linked list is not a palindrome linked list and we will return False.

Input/Output

We are also provided with a few examples.

Example 1: The given linked list is : 1 -> 2 -> 3 -> 2 -> 1.

Output: Yes, a palindrome linked list.

Example 2: The given linked list is : 5 -> 4 -> 3 -> 2 -> 5.

Output: No, not a palindrome linked list.

Constraints

$1<= n <= 10^5$, where n is the size of the linked list.

In some problems, you may find the number of test cases represented by t. So, we only need to call the checkPalindrome() function t-times.

Algorithm 1 - Using a Stack

A simple approach for checking whether a linked list is a palindrome linked list or not can be using a stack data structure. We can insert elements into the stack and then check whether the provided linked list is a palindrome or not.

Algorithm 2 - By Reversing the List

Another approach for checking whether a linked list is a palindrome linked list or not can be reversing the linked list and then comparing both the reversed and original linked list.

Algorithm

The pseudo-code for the same:

1. Reverse the linked list but first store the values of the original linked list data in a list or an array.
2. Traverse both the reversed linked list and the array containing the original linked list data. We would check whether the currently visited node of the original linked list is the same as the current index array value or not.
   • If both the values are the same then we can shift our checking to the next node of the linked list and the next index of the array.
   • Else, we would return False as the list is not a palindrome linked list.
3. Continue the above steps until the entire list is traversed or until a mismatch is found.

Code Implementation

Let us the code implementation of the same in various languages:

1. C++ Code

2. Java Code

3. Python Code

Output

In the above approach, we are reversing the linked list and before that, we are storing the original linked list values into an array.

Time complexity

We are traversing the entire linked list once for reversing the list (O(n)) and second time for checking (O(n)). So, the time complexity comes out to be [O(n) + O(n)] i.e. O(n), where n is the number of nodes present in the linked list.

Space complexity

We are traversing the linked list and storing the values in an array so the space complexity comes out to be O(n), where n is the size of the array.

Algorithm 3 - Using Recursion

Another approach for checking whether a linked list is a palindrome linked list or not can be recursively checking smaller portions (sub-lists) of the original linked list.

We will be using two pointers namely left and right pointers. We will be moving both the pointers recursively and checking if the sub-lists are a palindrome linked list or not.

Algorithm

As we know that whenever we recursively call a function, the function calls are stored on the recursion function stack. We can use this feature for checking the last element with the first element, a second element with the second last element, and so on.

So, we would traverse the linked list recursively and whenever we will reach the end of the linked list (i.e. until NULL is encountered), we can perform the checking. Now, when we are returning from the function calls, we will have the last element of the linked list so we can easily compare it with the first element of the linked list.

We will need the head pointer to access the first node of the list, so we will also pass the head pointer of the linked list.

Code Implementation

Let us the code implementation of the same in various languages:

1. C++ Code

2. Java Code

3. Python Code

Output

In the above approach, we are recursively traversing the end of the linked list and then check the last value with the first value, the second last value with the second value, and so on.

Time Complexity

We are traversing the entire linked list so the time complexity comes out to be O(n), where n is the number of nodes present in the linked list.

Space Complexity

Since we are using recursion, the recursive stack call will be considered. So the space complexity comes out to be O(n), where n is the number of nodes present in the linked list or the number of recursive function calls made.

Algorithm 4 - Using the Extra Data Structure

Another approach for checking whether a linked list is a palindrome linked list or not can be using an extra data structure such as an array or vector or list. We can simply start traversing the linked list and store the elements into an array and then check if the array is a palindrome or not. If the array is a palindrome then the linked list is also a palindrome linked list.

Algorithm

The pseudo-code for the same:

1. Start traversing the linked list nodes.
2. Insert all the nodes of the linked list node's data into the array.
3. When the entire linked list is stored in the array then check if the array is a palindrome or not. For checking whether the array is palindrome or not, we can follow the steps:
   • Check if the number in the current index is the same as the number in the n - current index - 1 of the array. If they are the same then continue the checking until the current index value is less than half of the size of the array (i.e. n/2). If the entire array is traversed and we have not found any mismatch then we can simply return True.
   • In case of any mismatch we must break and return False as there is no need to check further array elements.

Code Implementation

Let us the code implementation of the same in various languages:

1. C++ Code

2. Java Code

3. Python Code

Output

In the above approach, we are traversing the linked list and storing the values in an array or a list. We are then checking whether the array is a palindrome or not.

Time Complexity

We are traversing the entire linked list so the time complexity comes out to be O(n), where n is the number of nodes present in the linked list.

Space Complexity

We are traversing the linked list and storing the values in an array so the space complexity comes out to be O(n), where n is the size of the array.

Algorithm 5 - By Reversing the Second Half

Another efficient approach for checking whether a linked list is a palindrome linked list or not can be only reversing the second half of the input linked list and then checking both halves. In this approach, we will first find the mid element of the linked list and then reverse the second half of the linked list i.e. linked list starting from the mid element till the last. Now, we can easily check whether the first half and the second half are identical or not.

Algorithm

The pseudo-code for the same:

1. Find the middle element of the linked list.
2. Reverse the second half of the linked list starting from the middle element.
3. Traverse the list and check if the first half and the second half are identical or not.
   • If they are identical then the original linked list is a palindrome linked list and hence we will return True.
   • Else, the original linked list is not a palindrome linked list and hence we will return False.

Code Implementation

Let us the code implementation of the same in various languages:

1. C++ Code

2. Java Code

3. Python Code

Output

In the above approach, we are reversing the second half of the input linked list and then checking both halves.

Time complexity

We are traversing the entire linked list. Once for getting the mid element of the linked list (O(n)). After that we are traversing the list for checking (O(n)). So, the time complexity comes out to be [O(n) + O(n)] i.e. O(n), where n is the number of nodes present in the linked list.

Space complexity

We are not using any extra space so the space complexity comes out to be O(1).