Palindrome Linked List - Python Solution

1. Introduction

The "Palindrome Linked List" problem is a common question in algorithm interviews, combining concepts of linked lists and palindromes. A palindrome is a sequence that reads the same backward as forward. This problem involves determining if the values in a singly linked list form a palindrome. It tests one's ability to manipulate and traverse linked lists efficiently.

Problem

Given the head of a singly linked list, the task is to return true if the list is a palindrome or false otherwise.

2. Solution Steps

1. Find the middle of the linked list using the fast and slow pointer technique.

2. Reverse the second half of the list.

3. Compare the nodes of the first half and the reversed second half.

4. If all corresponding nodes are equal, the list is a palindrome.

5. Restore the list to its original order by reversing the second half again (optional).

6. Return true if a palindrome, otherwise false.

3. Code Program

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

def isPalindrome(head):
    def reverseList(head):
        prev, current = None, head
        while current:
            next_temp = current.next
            current.next = prev
            prev, current = current, next_temp
        return prev

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

    # Reverse the second half
    second_half = reverseList(slow)

    # Compare
    first_half, second_half_copy = head, second_half
    while second_half:
        if first_half.val != second_half.val:
            return False
        first_half, second_half = first_half.next, second_half.next

    # Restore the original list (Optional)
    reverseList(second_half_copy)

    return True

# Example Usage
# Creating list for demonstration: [1 -> 2 -> 2 -> 1]
head = ListNode(1, ListNode(2, ListNode(2, ListNode(1))))
print(isPalindrome(head))  # Output: True

# List not a palindrome: [1 -> 2]
head = ListNode(1, ListNode(2))
print(isPalindrome(head))  # Output: False

Output:

True
False

Explanation:

1. ListNode Class: Represents each node in the linked list.

2. Middle of List: Fast and slow pointers are used to find the middle of the list.

3. Reverse Second Half: The second half of the list is reversed for comparison.

4. Palindrome Check: The first and second halves are compared to check if the list forms a palindrome.

5. List Restoration: Optionally, the list can be restored to its original order.

6. Efficient Solution: The approach ensures an O(n) time complexity and O(1) space complexity.

7. Result: The function returns true if the list is a palindrome, otherwise false.