Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Problem Challenge 1: Palindrome LinkedList
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Given the head of a Singly LinkedList, write a method to check if the LinkedList is a palindrome or not.

Your algorithm should use constant space and the input LinkedList should be in the original form once the algorithm is finished. The algorithm should have O(N) time complexity where ‘N’ is the number of nodes in the LinkedList.

Example 1:

Input: 2 -> 4 -> 6 -> 4 -> 2 -> null
Output: true

Example 2:

Input: 2 -> 4 -> 6 -> 4 -> 2 -> 2 -> null
Output: false

Constraints:

  • The number of nodes in the list is in the range [1, 10^5].
  • 0 <= Node.val <= 9

Solution

As we know, a palindrome LinkedList will have nodes values that read the same backward or forward. This means that if we divide the LinkedList into two halves, the node values of the first half in the forward direction should be similar to the node values of the second half in the backward direction. As we have been given a Singly LinkedList, we can’t move in the backward direction. To handle this, we will perform the following steps:

  1. We can use the Fast & Slow pointers method similar to Middle of the LinkedList to find the middle node of the LinkedList.
  2. Once we have the middle of the LinkedList, we will reverse the second half.
  3. Then, we will compare the first half with the reversed second half to see if the LinkedList represents a palindrome.
  4. Finally, we will reverse the second half of the LinkedList again to revert and bring the LinkedList back to its original form.

Here is the visual representation of this algorithm for Example-2:

Image

Code

Here is what our algorithm will look like:

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • Finding the middle of the linked list: The algorithm uses the two-pointer technique (slow and fast pointers) to find the middle of the linked list. Both pointers traverse the list once, so this phase takes O(N) time, where N is the number of nodes in the linked list.

  • Reversing the second half: After finding the middle, the algorithm reverses the second half of the list. This also takes O(N/2) time, which simplifies to O(N).

  • Comparing both halves: Once the second half is reversed, the algorithm compares the values of the first half and the reversed second half. This comparison takes O(N/2) time, which simplifies to O(N).

  • Reversing the second half back: To restore the original list structure, the algorithm reverses the second half again. This takes O(N/2) time, which simplifies to O(N).

Overall time complexity: O(N).

Space Complexity

  • Reversing the second half: The algorithm modifies the linked list in place, and no extra space is required other than the pointers used during the traversal and reversal operations.
  • The algorithm only uses a few extra pointers (slow, fast, prev, etc.), which take constant space.

Overall space complexity: O(1) (constant space).

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible