Palindrome Linked List

Question:

Given a singly linked list, determine if it is a palindrome.

You may modify the linked list in-place and O(1) extra space is allowed.

Example:

Input: 1 -> 2 -> 3 -> 2 -> 1

Output: True

Answer:

To determine whether a singly linked list is a palindrome, we can use a two-pointer approach along with some additional steps. Here is the step-by-step explanation of the algorithm:

1. Edge case: If the given linked list is empty or only contains one node, it is considered a palindrome. In such cases, we can directly return True.

2. Find the middle: Use a slow and a fast pointer to find the middle element of the linked list. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. When the fast pointer reaches the end of the linked list, the slow pointer will be at the middle (or middle-left in case of an odd number of nodes).

3. Reverse the second half: After finding the middle, reverse the second half of the linked list. To do this, we can use a helper function that takes the head of the second half as input and returns the head of the reversed second half.

4. Compare the halves: Compare each node of the first half (starting from the head) with the corresponding node of the reversed second half. If any pair of nodes does not match, the linked list is not a palindrome and we can return False.

5. Restore the original linked list (optional): If it is required to restore the original linked list after the function execution, reverse the second half again using the helper function. This step is optional and depends on the constraints of the problem.

6. Return the result: If all the nodes pairings match, the linked list is a palindrome and we can return True.

Here is the implementation of the above algorithm in Python:

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

def isPalindrome(head):
    # Edge case: Empty or single node linked list
    if not head or not head.next:
        return True

    # Helper function to reverse a linked list
    def reverseList(node):
        prev = None
        curr = node
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        return prev

    # 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 of the linked list
    second_half = reverseList(slow)

    # Compare the first half with the reversed second half
    first_half = head
    while second_half:
        if first_half.val != second_half.val:
            return False
        first_half = first_half.next
        second_half = second_half.next

    # Optional: Restore the original linked list
    reverseList(reverseList(slow))

    return True

The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list. This is because we need to traverse the linked list twice: once to find the middle and once to compare the halves. The space complexity is O(1) since we only use a few pointers to manipulate the linked list.