Palindrome Linked List Leetcode Problem 234 [Python Solution]

In this post, we're going to tackle the LeetCode problem 234 – Palindrome Linked List This is an "Easy" level problem that falls under the "Linked List" category and is often used as an interview question by companies like Google.

We will provide a Python solution to this problem, along with a detailed explanation of the approach and its time and space complexity.

So, let's dive right in!

Problem Overview

The problem statement is as follows: Given the head of a singly linked list, you need to determine whether the linked list is a palindrome or not.

In other words, you need to check if the linked list reads the same forwards and backwards.

To understand this problem better, let's look at an example:

Example 1:

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

Output: true

Example 2:

Input: head = [1,2]

Output: false

In the first example, the input linked list [1,2,2,1] is a palindrome because it reads the same forwards and backwards.

In the second example, the input linked list [1,2] is not a palindrome because it doesn't read the same in reverse order.

Understanding Palindrome Linked List Constraints

Before we dive into the solution, let's understand the constraints and requirements of this problem:

• The number of nodes in the linked list is in the range [1, 10^5].
• The values of the nodes are integers in the range [0, 9].

Now, let's discuss two different approaches to solving this problem: a brute-force approach and an efficient approach using two pointers.

Palindrome Linked List LeetCode Problem Solution

1. Bruteforce Approach

One straightforward way to solve this problem is to convert the linked list into an array and then check if the array is a palindrome.

Here's how you can do it in Python:

def isPalindrome(self, head: ListNode) -> bool:
    # Convert the linked list into an array
    nums = []
    while head:
        nums.append(head.val)
        head = head.next

    # Check if the array is a palindrome
    left, right = 0, len(nums) - 1
    while left < right:
        if nums[left] != nums[right]:
            return False
        left += 1
        right -= 1
    return True

This approach is simple and works, but it requires extra memory to store the array.

Therefore, it's not optimal in terms of space complexity.

We can improve the space complexity to O(1) by using a two-pointer approach.

2. An Efficient Approach with Two Pointers

The efficient solution utilizes two pointers, one moving at double the speed of the other to find the middle of the linked list.

Once the middle is found, the second half of the linked list is reversed, and then both halves are compared to check if they form a palindrome.

Here's the Python code for this efficient solution:

def isPalindrome(self, head: ListNode) -> bool:
    fast = head
    slow = head

    # Find the middle (slow)
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next

    # Reverse the second half
    prev = None
    while slow:
        tmp = slow.next
        slow.next = prev
        prev = slow
        slow = tmp

    # Check if it's a palindrome
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next
    return True

This approach is both time and space-efficient as it doesn't require extra memory to store the entire linked list in an array.

It leverages the properties of linked lists to determine if it's a palindrome or not.

Time and Space Complexity

Now, let's analyze the time and space complexity of the efficient two-pointer solution.

• Time Complexity: O(n)

  • The first loop that finds the middle of the linked list runs in O(n/2) time, which simplifies to O(n).
  • The second loop that checks for the palindrome also runs in O(n/2) time.
  • Overall, the time complexity is O(n).

• Space Complexity: O(1)

  • We use a constant amount of extra space, mainly for pointers and temporary variables.

The space complexity is O(1).

Reasoning Behind Our Approach

The reasoning behind the efficient two-pointer approach is based on the idea that finding the middle of the linked list allows us to split it into two parts: the first half and the reversed second half.

By comparing these two halves, we can determine if the linked list is a palindrome.

• We use two pointers, fast and slow, to find the middle of the linked list.

The fast pointer moves twice as fast as the slow pointer, which ensures that the slow pointer reaches the middle when the fast pointer reaches the end.
– Once we find the middle, we reverse the second half of the linked list.

This is done by iteratively updating the next pointers of the nodes, effectively reversing the direction of the links.
– After reversing the second half, we compare the values of nodes from the first half with the reversed second half.

If they match for all nodes, the linked list is a palindrome, and we return True.

Otherwise, we return False.

This approach is efficient because it doesn't require additional memory for storing the entire linked list as an array.

It also leverages the properties of linked lists to solve the problem in O(n) time.

Related Interview Questions By Company:

• Island Perimeter LeetCode
• Path Sum LeetCode
• Shift 2D Grid LeetCode

Related Interview Questions By Difficulty:

• Copy List With Random Pointer LeetCode
• Middle Of The Linked List LeetCode
• Partition List LeetCode

Related Interview Questions By Category:

• Number Of Islands LeetCode
• Hand Of Straights LeetCode
• Longest Common Subsequence LeetCode

Conclusion

In this blog post, we tackled the LeetCode problem 234 – Palindrome Linked List We provided two different solutions: a brute-force approach using an array and an efficient approach using two pointers.

The efficient approach has a time complexity of O(n) and a space complexity of O(1), making it an optimal solution for this problem.

We encourage you to try this problem on LeetCode to practice your coding skills and problem-solving abilities.

If you have any questions, suggestions, or comments, please feel free to share them below.

We appreciate your feedback!

Question Link: Palindrome Linked List on LeetCode

If you found this post helpful, don't forget to like, share, and engage for more neat code solutions!

Happy coding!