How do you determine if a linked list is a palindrome efficiently, optimizing for space and time complexity, potentially by reversing the second half of the list and comparing it with the first half of the original list, given the head of the list?

You are given the head of a singly linked list. Implement a function to determine if the linked list is a palindrome. A palindrome is a sequence that reads the same backward as forward.

Example 1:

• Input: head = [1, 2, 2, 1]
• Output: true

Example 2:

• Input: head = [1, 2, 3, 2, 1]
• Output: true

Example 3:

• Input: head = [1, 2]
• Output: false

Constraints:

• The number of nodes in the list is in the range [1, 10^5].
• 0 <= Node.val <= 9

Your function should efficiently determine if the linked list forms a palindrome. Consider space and time complexity optimizations. For instance, think about how you can achieve this without using extra space (O(1) space complexity) or minimizing the time complexity to O(n). Can you solve this by reversing the second half of the list and comparing it with the first half?

Palindrome Linked List

This problem asks us to determine if a given singly linked list is a palindrome. A palindrome reads the same forwards and backward. Let's explore a few approaches to solve this efficiently.

Example Cases

• Input: head = [1, 2, 2, 1]
• Output: true
• Input: head = [1, 2, 3, 2, 1]
• Output: true
• Input: head = [1, 2]
• Output: false

1. Brute Force Approach

The most straightforward approach is to copy the linked list values into an array and then use two pointers to check if the array is a palindrome.

Code (Python)

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

def isPalindrome_brute_force(head):
    vals = []
    current = head
    while current:
        vals.append(current.val)
        current = current.next
    
    left, right = 0, len(vals) - 1
    while left < right:
        if vals[left] != vals[right]:
            return False
        left += 1
        right -= 1
    return True

2. Optimal Approach: Reverse Second Half

A more efficient approach involves reversing the second half of the linked list and then comparing it with the first half. This method achieves O(1) space complexity.

Algorithm

1. Find the Middle: Use the slow and fast pointer technique to find the middle of the linked list.
2. Reverse the Second Half: Reverse the linked list starting from the middle.
3. Compare: Compare the first half and the reversed second half.
4. Restore (Optional): Reverse the second half again to restore the original linked list (if needed).

Code (Python)

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: # Empty list or single element list
        return True

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

    # 2. Reverse the second half
    prev, curr = None, slow
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

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

    return True

Big(O) Runtime Analysis

• Brute Force: O(n) because we iterate through the linked list once to copy the values into the array, and then we iterate through approximately half of the array to check if it's a palindrome.
• Optimal (Reverse Second Half): O(n) because we traverse the list to find the middle, reverse the second half, and then compare the two halves.

Big(O) Space Usage Analysis

• Brute Force: O(n) because we store the linked list values in an array.
• Optimal (Reverse Second Half): O(1) because we perform the reversal in-place, using a constant amount of extra space.

Edge Cases

• Empty List: An empty linked list is considered a palindrome.
• Single Element List: A single-element list is also a palindrome.
• List with Even Length: The algorithm should correctly handle lists with an even number of elements.
• List with Odd Length: The algorithm should correctly handle lists with an odd number of elements. In this case, the middle element doesn't need to be compared.

Handling Edge Cases in Code

• The optimal solution handles the empty list and single element list cases by returning True at the beginning of the function.
• The slow and fast pointer method naturally handles both even and odd length lists, ensuring the correct middle node is found.