# Leetcode – Palindrome Linked List Solution in Python

## 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

# Convert linked list to array
arr = []
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

# Find the middle of the linked list
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
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

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.