Leetcode – Palindrome Linked List Solution in Python

Spread the love

Introduction

The Palindrome Linked List problem is a popular algorithm question on LeetCode and is frequently asked during coding interviews. It falls under the category of linked lists, which is a fundamental data structure in computer science. This article aims to provide an in-depth analysis of the problem, various approaches to solve it, and their respective Python implementations. We will also delve into the time and space complexities of each approach.

Problem Statement

The problem is as follows:

Given the head of a singly linked list, return True if it is a palindrome.

Input

  • head: A reference to the head node of a singly linked list with integer values.

Output

  • A boolean value indicating if the linked list is a palindrome.

Understanding the Palindrome Concept

A palindrome is a sequence that reads the same backward as forward. For example, “level” and “abccba” are palindromes. In the context of a linked list, a palindrome linked list means that the sequence of values in the linked list is the same when read from the head to the tail and from the tail to the head.

Approach 1: Convert to Array

  1. Traverse the linked list and store each element in an array.
  2. Use two pointers approach to compare the elements at the beginning and the end of the array, incrementally moving towards the center.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def isPalindrome(head):
    # Convert linked list to array
    arr = []
    current = head
    while current:
        arr.append(current.val)
        current = current.next
    
    # Check if array is a palindrome
    left, right = 0, len(arr) - 1
    while left < right:
        if arr[left] != arr[right]:
            return False
        left += 1
        right -= 1
    
    return True

Time Complexity

The time complexity is O(n), where n is the number of elements in the linked list.

Space Complexity

The space complexity is also O(n) because we store the elements in an array.

Approach 2: Reverse Second Half In-Place

  1. Find the middle of the linked list.
  2. Reverse the second half of the linked list.
  3. Compare the first half and the reversed second half.
  4. (Optional) Restore the original structure by reversing the second half back.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def isPalindrome(head):
    # Find the middle of the linked list
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    # Reverse the second half
    prev = None
    while slow:
        temp = slow.next
        slow.next = prev
        prev = slow
        slow = temp
    
    # Compare the first half and the reversed second half
    first, second = head, prev
    while second:
        if first.val != second.val:
            return False
        first = first.next
        second = second.next
    
    return True

Time Complexity

The time complexity is O(n), where n is the number of elements in the linked list.

Space Complexity

The space complexity is O(1) because we reverse the second half in-place without using additional space.

Approach 3: Recursion

  1. Use recursion to reach the end of the linked list.
  2. As the stack unwinds, compare the current node with the corresponding node from the head of the list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def isPalindrome(head):
    front_pointer = head

    def recursively_check(current_node=head):
        nonlocal front_pointer
        if current_node is not None:
            if not recursively_check(current_node.next):
                return False
            if current_node.val != front_pointer.val:
                return False
            front_pointer = front_pointer.next
        return True
    
    return recursively_check()

Time Complexity

The time complexity is O(n), where n is the number of elements in the linked list.

Space Complexity

The space complexity is O(n) due to the recursive call stack.

Conclusion

In this article, we discussed the Palindrome Linked List problem on LeetCode and explored three different approaches to solve it – converting to an array and using a two-pointer approach, reversing the second half in-place, and using recursion. We also analyzed the time and space complexities of each approach. The in-place reversal method is especially useful when space complexity needs to be minimized. Understanding these approaches and the underlying concepts is not only vital for solving variations of this problem but also forms the foundation for solving other complex problems involving linked lists.

Leave a Reply