How would you check if a linked list is a palindrome?

Checking if a linked list is a palindrome involves several steps. Here’s a step by step walkthrough.

1. Find the middle of the linked list.

2. Reverse the second half of the linked list.

3. Check if the first half and second half are equal (considering that half denotes the first half if list has odd elements).

4. If they are, then the linked list is a palindrome.

5. Reverse the second half again to restore the original linked list.

For the sake of the explanation, assume the linked list is: [1 -> 2 -> 3 -> 2 -> 1].

##### 1. Find the middle of the linked list

To identify the middle of the linked list, an efficient strategy involves using two pointers, namely ‘slow‘ and ‘fast‘. Initially, both will point to the head. The ‘slow‘ pointer will move one step at a time, whereas the ‘fast‘ will move two steps. When ‘fast‘ pointer gets to the end, the ‘slow‘ pointer will be in the middle of the list.

Take a look at this Python example:

def find_middle(head):
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow

##### 2. Reverse the second half of the linked list

Now, let’s create a function ‘reverse‘ which will reverse the order of the second half of the linked list.

def reverse(second_half):
    prev = None
    while second_half:
        next_node = second_half.next
        second_half.next = prev
        prev = second_half
        second_half = next_node
    return prev

##### 3. Check if both halves are equal

Next, we’ll compare each node’s value in the first half with the nodes in the reversed second half. If all are identical, the list is a palindrome.

def is_palindrome(first_half, second_half):
    while second_half:
        if first_half.val != second_half.val:
            return False
        first_half = first_half.next
        second_half = second_half.next
    return True

##### 4. Reverse the second half again

Once we have determined if the linked list was a palindrome, we should restore its original order by reversing the second half again.

5. The full implementation of the Python function including all steps is:

def is_list_palindrome(head):

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

    # Step 2: Reverse second half
    prev = None
    while slow:
        next_node = slow.next
        slow.next = prev
        prev = slow
        slow = next_node
    second_half = prev

    # Step 3: Check palindrome
    while second_half: 
        if head.val != second_half.val:
            return False
        head = head.next
        second_half = second_half.next
    
    return True

This algorithm runs in linear time O(N) because we only traverse the linked list a constant number of times. The space complexity is constant, O(1), as we are only using a few extra variables and not any extra space that scales with the input size.