top of page
  • LinkedIn
  • Facebook
  • YouTube
  • Twitter
  • Instagram
  • Pinterest
  • Tumblr
  • Vkontakte

234. Palindrome Linked List - LeetCode Fastest Solution

Writer's picture: Code RecipeCode Recipe

Hello Code Recipian! Here we meet again with yet another LeetCode problem solution. Today let's solve LeetCode problem 234. Palindrome Linked List.


Let's check out the problem statement!


Problem Statement: Palindrome Linked List


Given the head of singly linked list, return true if it is a palindrome, false otherwise.


Note: A palindrome is a sequence that reads the same forward and backward.


Example 1:

Example 1 image

Input: head = [1, 2, 2, 1]

Output: true

Explanation: Given linked list node values form a palindrome. Hence output is true.


Example 2:

Example 2 image

Input: head = [1, 2, 3, 4]

Output: false

Explanation: Given linked list is not a palindrome.


Solution


This is another singly linked list problem which can be solved optimally using the slow and fast pointer technique which we have discussed in some of our previous articles like 141. Linked List Cycle, 142. Linked List Cycle II, Finding The Middle Element.


Algorithm


Below is detailed explanation for the working of the algorithm:

  1. Find the middle node: Initialize two pointer variables: slow, fast. Initially both slow and fast point to the head node.

    Traverse through the linked list using slow, fast pointers. In each iteration perform the following steps:

    1. Move slow pointer ahead by one node.

    2. Move fast pointer ahead by two nodes.

    3. When the fast pointer reaches the last node, the slow pointer will reach the middle node of the linked list.

  2. Reverse second half of linked list: Now that slow pointer points to the middle node of the linked list, the next step is to reverse the second half the list i.e. all nodes starting from slow pointer. If you are looking for a detailed explanation on how to reverse a linked list, you can check our article on How To Reverse A Linked List.

    The idea behind reversing the 2nd half is that, once we have the second half reversed, we can simultaneously traverse the list from two extreme ends and compare corresponding node value to check if it is a palindrome or not.

  3. Compare first and second half: The reverse() function returns the last node (in the original list) as the head node for the reversed second half. Let's call this l2Head.

    1. To begin with initialize two pointers variables: curr1 and curr2. Initially, curr1 points to the head node of the first half and curr2 points to the l2Head.

    2. Initialize a boolean result variable to store our final result (i.e. palindrome or not). Initially it is set to true.

    3. Now traverse through the first and second lists using the curr1 and curr2 pointers respectively. In each iteration,

      1. Compare the corresponding curr1 and curr2 node values.

      2. If at any point during the traversal, if node values do not match, set result to false and stop traversal.

  4. Revert second half to original form: Now since we are done processing the linked list, we restore the second half that we reversed earlier, by reversing it back again.

  5. Return final result: Return value in result as the final result.


Simulation



Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses:





Code


Go Solution


Python Solution

Java Solution

JavaScript Solution

TypeScript Solution

C++ Solution

C# Solution

C Solution

PHP Solution

Kotlin Solution

Swift Solution

Ruby Solution

Scala Solution

Rust Solution


Complexity Analysis


Time Complexity


Finding the middle node:

We need to traverse through the list using slow and fast pointer in order to get the middle node. So the time complexity is O(n).


Reversing the second half:

If n is the number of nodes in the given linked list, it takes n/2 iterations to reverse the second half. So the time complexity is O(n).


Check if palindrome:

Checking for palindrome also takes O(n) time as we have to compare every node value in first half with the corresponding value in the second half.


Restoring the list:

Before returning result we revert the list to original form. This also takes O(n) time.


Overall time complexity:

Considering all the above factors, the overall time complexity of this solution is O(n) + O(n) + O(n) + = O(n).


Space Complexity


Since we only manipulate the pointers in the given linked list and do not use any extra space, the space complexity is O(1).


That concludes this article. But hey! Don't stop here! Master more problems on linked lists and palindrome. Explore now:

Code Recipe Limited Time Offer: Enjoy a 100% discount on the Code Recipe Membership Plan. Sign up now to access exclusive premium content for free. Act fast—offer only available for a limited time - Join now.


Recent Posts

See All

1 Comment


Code Recipe
Code Recipe
Jan 18
•

Hello Coders!


Code Recipe is now on YouTube! For videos on latest topic visit our YouTube channel: Code Recipe 


Visit Now: https://www.youtube.com/@coderecipeofficial


Do not forget to subscribe to our channel if you find the videos useful. Your support means a lot to us!


Happy Learning. Ba bye! 😊

Code Recipe YouTube Channel

Like

We are now on YouTube!

Prefer learning through videos? No worries! Visit Code Recipe on YouTube now.

bottom of page