Palindrome Linked List Leetcode Solution

In the problem "Palindrome Linked List", we have to check whether a given singly integer linked list is a palindrome or not.

Example

List = {1 -> 2 -> 3 -> 2 -> 1}

true

Explanation #1: The list is palindrome as all elements from the start and back are the same in value.

List = {1 -> 2 -> 3 -> 4 -> 5}

false

Explanation #2: The list is not palindrome as elements from back and forth are not the same.

Approach(Recursion)

This is easy to notice that we need to have the details of the nodes from the back of the array for checking palindrome properties. In this case, we have a singly linked list meaning that we can only iterate forward to reach any node. Thus, it becomes important to use some data structure to hold the nodes from the back, e.g. stack is a possible option as it keeps the most recent node at the top. We can also use recursion similarly. Recursion is an elegant to get the node values in reverse order. Consider the below general pseudocode for better understanding:

inorderTraversal(root)

{

if(root == null)

return;

inorderTraversal(root.left);

print(root.data);

inorderTraversal(root.right);

}

The above code first prints left nodes in the tree because we recursively call the function to go to left children of any root before printing the value of the node itself. Similarly, we can use recursion to go to the last nodes first and when the function will backtrack, we will be getting the node values in reverse order.

 

www.tutorialcup.com/leetcode-solutions/palindrome-linked-...

Done