Problem

Submissions

Hints & solutions

Discuss

Check If Linked List Is Palindrome

Easy

0/40

Average time to solve is 15m

Contributed by

91 upvotes

Asked in companies

Problem statement

You are given a Singly Linked List of integers. You have to return true if the linked list is palindrome, else return false.

A Linked List is a palindrome if it reads the same from left to right and from right to left.

Example:

The lists (1 -> 2 -> 1), (3 -> 4 -> 4-> 3), and (1) are palindromes, while the lists (1 -> 2 -> 3) and (3 -> 4) are not.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first and only line contains the linked list of elements separated by a single space and terminated by -1. 
Hence -1 would never be a list element.

Output Format :

Print “True” if the given linked list is a palindrome. Else, print “False”.

Note:

You do not need to print anything. 
It has already been taken care of. Just implement the given function.

Sample Input 1:

1 2 2 1 -1

Sample Output 1:

True

Explanation for Sample Input 1:

The given list is a palindrome.

Sample Input 2:

3 2 1 -1

Sample Output 2:

False

Constraints :

1 <= 'N' <= 5 * 10^4
-10^9 <= 'data' <= 10^9 and 'data' != -1

Where 'N' is the number of nodes in the linked list and ‘data’ represents the value of the list's nodes.

Time Limit: 1sec

Hint 1

Hint 2

Hint 3

Can you think of a data structure which will help you to visit the nodes in reverse?

Approaches (3)

Approach 1

Approach 2

Approach 3

Using Stack

The idea is to store the list values in a stack and then compare the values in the list with the values in the stack.

Algorithm:

Traverse the list from head to tail and push every node in the stack.
Make a pointer ‘cur’ which initially points to the head node.
If value at ‘cur’ is not equal to the top element of the stack, then the given list is not a palindrome
Else, move the ‘cur’ pointer to its next node and pop the top element from the stack.
If stack is empty, then the given list is a palindrome
Else, repeat the steps 3 to 6.

Time Complexity

O(N), Where N is the number of nodes in the linked list.

We are traversing the list twice and traversing a list takes O(N) time, thus the final time complexity is O(2 * N) = O(N).

Space Complexity

O(N), Where N is the number of nodes in the linked list.

We are storing node values in a stack which will take O(N) extra space.

(75% EXP penalty)

(100% EXP penalty)

Check If Linked List Is Palindrome

Console