Check if a Singly linked list is palindrome or not

Three Solutions Discussed

  1. Using Recursion
  2. Iterative Approach-By reversing the list
  3. Using Stack

Key Takeaway after reading this blog

  1. Application of recursion and stack on the linked list
  2. 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.

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

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.

  • 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.

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 .

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

Algorithm Code C++

Algorithm Analysis

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

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.

Problems for practice — Backtracking/DFS Approach

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Shubham Kumar Gupta

Shubham Kumar Gupta

Software Engineer | Coding Enthusiasts | Data Science