# Check if a Singly linked list is palindrome or not

coding interview problem

**Difficulty Level**

Medium

**Asked In**

Amazon,Adobe,Microsofy,Adobe

# Three Solutions Discussed

- Using Recursion
- Iterative Approach-By reversing the list
- Using Stack

# Key Takeaway after reading this blog

- Application of recursion and stack on the linked list
- Learn about next pointer of linked list and its interchanging concept of pointers .

# Let’s understand the problem

Given a linked list of either even or odd length . we have to tell whether this linked list forms a palindrome or not.

**Example:**

Input : 1->2->2->1

Output : yesInput : 1->3->2->3->1

Output : yes Input : 1->2->3->2->5

Output : no

**Explanation : **Input 1 & 2 values of linked list form a palindrome while values of Input 3 didn’t form a palindrome

# 1. Using Recursion

# Algorithm Idea

Here Idea is to use the recursion stack of the compiler to compare the first and last element , second and second last and so on such that we find out whether the linked list is palindrome or not.

At any point of time where this comparison return false ,we get the result as false and if no false is return then the given linked list is palindrome.

**Solution Steps :**

- Recursively traverse the entire linked list to get the last node as a rightmost node.
- Compare the first node (left node) with the right node. If both are having same data value then recursively call for the sub-list as to check if the sub-list is a palindrome or not.(by increasing the head pointer to points to its next and recursive call return will take care of the rightmost value)
- If all the recursive calls are returning true, it means the Linked List given is a palindrome else it is not a palindrome.

# Algorithm Code C++

# Algorithm Analysis

Time Complexity: O(n) ( As Two linked list iteration exist one for the recursive call that goes on to the rightmost element and second iteration that is starting from the leftmost element to compare the left and right element and their subpart as well.

Space Complexity = O(n)( If we consider the recursive stack space of the compiler)

# Possible questions by the interviewer

- Dry run an example to explain ur logic
- what modification need to be done if linked list value is string rather than char or int?
- can we do it iteratively?

# 2. Iterative Approach — By reversing the linked list

# Algorithm Idea

In this approach, we iterate to the middle of the linked list and then reverse the second half of it . After that we start to compare the head of the linked list and the reversed second half of the linked list .

**Intution** : suppose we have linked list : 1->2->3->2->1

(i) we go to the middle of the linked list : i.e; 3 and reverse the second half

(ii) second half now become : 1->2 .

(iii) change the next pointer value of the mid to NULL i.e: mid->next = NULL

(iv) start comparing the head of the linked list and second half of the reversed linked list i.e : 1->2->3 & 1->2

(v) Do the comparision until either one gets empty or comparision returns false value.

# Algorithm Code C++

# Algorithm Analysis

**Time Complexity**: O(n/2) + O(n/2) + O(n/2) = O(3n/2) ~ O(n)

First O(n/2) for finding mid of linked list

Second O(n/2) for reversing the second half of linked list

Third O(n/2) for comparing the first and the second half**Space Complexity **= O(1) (because we are doing the in-place changing)

# Possible questions by the interviewer

- Dry run an example to explain ur logic
- what edge cases need to be handled in case of odd and even length linked list
- Give me a iterative solution without changing the linked list.

# 3. Using Stack

# Algorithm Idea

This is one of the simplest approaches in which we simply push every element to a stack which stores the element in **LIFO**(Last in first out order) order and after that we again start the comparision from the head of the linked list and the top element of the stack

If stack get’s empty or linked list become NULL , then there is no comparision conflict and hence our linked list will be a palindrome

Else linked list is not a palindrome.

# Algorithm Code C++

# Algorithm Analysis

Time Complexity: O(n) + O(n) = O(2n) = O(n)(approximately) .

As this approach involves two iteration of the linked list .

Space Complexity = O(n)(as we are storing element of the linked list in the array)

# Possible questions by the interviewer

- How stack is implemented in c++.
- properties of stack
- what is linked list value is string rather than char or int. How you modify your algorithm.