Palindrome Linked List - Python Solution

1. Introduction

The "Palindrome Linked List" problem is an interesting challenge that tests one's ability to manipulate linked lists. A palindrome is a sequence that reads the same forward and backward, and this problem requires checking if a singly linked list forms a palindrome. It combines concepts of linked list traversal, reversal, and comparison.

Problem

Given the head of a singly linked list, the objective is to determine whether the list forms a palindrome. The function should return true if the list is a palindrome, and false otherwise.

2. Solution Steps

1. Traverse the list to find its length.

2. Identify the midpoint of the list.

3. Reverse the second half of the list.

4. Compare the first half and the reversed second half node by node.

5. If all corresponding nodes match, the list is a palindrome.

6. Optionally, reverse the second half again to restore the list's original order.

7. Return true if a palindrome is detected, otherwise false.

3. Code Program

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def isPalindrome(head):
    if not head or not head.next:
        return True

    # Find the length of the list
    length, current = 0, head
    while current:
        length += 1
        current = current.next

    # Find the midpoint and reverse the second half
    mid = length // 2
    prev, current = None, head
    for _ in range(mid):
        prev, current = current, current.next
    second_half, prev.next = prev, None

    # Reverse the second half
    prev, current = None, current
    while current:
        next_node = current.next
        current.next = prev
        prev, current = current, next_node
    second_half_reversed = prev

    # Compare the two halves
    first_half, second_half = head, second_half_reversed
    while second_half:
        if first_half.val != second_half.val:
            return False
        first_half, second_half = first_half.next, second_half.next

    return True

# Example Usage
head = ListNode(1, ListNode(2, ListNode(2, ListNode(1))))
print(isPalindrome(head))  # Output: True
head = ListNode(1, ListNode(2))
print(isPalindrome(head))  # Output: False

Output:

True
False

Explanation:

1. ListNode Class: Represents nodes in the linked list.

2. List Length Calculation: Traverses the list to find its total length.

3. Midpoint Identification: Determines the middle of the list for division.

4. Reversal of Second Half: Reverses the second half of the list for comparison.

5. Palindrome Check: Compares the first half and the reversed second half node by node.

6. Restoration (Optional): Restores the second half to its original order.

7. Efficient Algorithm: Provides an O(n) time complexity solution with O(1) space complexity.

8. Result: Returns true if the list is a palindrome, otherwise false.