Problem Description

You are given the head of a singly linked list. Your task is to determine whether the linked list forms a palindrome when reading the values from start to end.

A palindrome reads the same forwards and backwards. For example, a linked list with values 1 -> 2 -> 2 -> 1 is a palindrome because reading from left to right gives [1, 2, 2, 1] and reading from right to left also gives [1, 2, 2, 1].

The function should return true if the linked list is a palindrome, and false otherwise.

The solution uses a two-pointer technique to find the middle of the linked list. Once the middle is found, the second half of the list is reversed in-place. Then, both halves are compared node by node. The algorithm works as follows:

1. Use slow and fast pointers to locate the middle of the linked list. The slow pointer moves one step at a time while the fast pointer moves two steps.

2. Reverse the second half of the linked list starting from the node after the slow pointer.

3. Compare the values of nodes from the first half with the reversed second half. If all corresponding values match, the linked list is a palindrome.

4. Return true if all values match, false if any mismatch is found.

For example:

• Input: 1 -> 2 -> 3 -> 2 -> 1 returns true
• Input: 1 -> 2 -> 3 -> 4 returns false

Intuition

To check if a linked list is a palindrome, the straightforward approach would be to store all values in an array and check if the array reads the same forwards and backwards. However, this requires O(n) extra space.

The key insight is that we only need to compare the first half with the second half. If we can somehow read the second half in reverse order, we can compare it with the first half directly.

Since we can't traverse a singly linked list backwards, we need to physically reverse the second half. This leads us to three main challenges:

1. Finding the middle point: We need to split the list into two halves. The fast and slow pointer technique elegantly solves this - when the fast pointer reaches the end (moving twice as fast), the slow pointer will be at the middle.

2. Reversing the second half: Once we find the middle, we can reverse the links in the second half. This is a standard linked list operation where we iterate through nodes and reverse their next pointers.

3. Comparing both halves: After reversing, we can traverse both halves simultaneously from their respective starts, comparing values at each step.

The beauty of this approach is that it achieves O(1) space complexity by modifying the linked list structure temporarily. We're essentially transforming the problem from "check if a sequence is a palindrome" to "check if two sequences are identical" by cleverly manipulating the list structure itself.

This technique of using the list's own structure to solve the problem without extra space is a common pattern in linked list problems where we want to optimize space complexity.

Solution Approach

The solution implements the fast and slow pointer technique to find the middle of the linked list, then reverses the second half for comparison.

Step 1: Find the Middle Node

slow, fast = head, head.next
while fast and fast.next:
    slow, fast = slow.next, fast.next.next

We initialize slow at the head and fast at the second node. The fast pointer moves two steps while slow moves one step. When fast reaches the end, slow will be at the middle. For even-length lists, slow stops at the last node of the first half. For odd-length lists, slow stops at the middle node.

Step 2: Reverse the Second Half

pre, cur = None, slow.next
while cur:
    t = cur.next
    cur.next = pre
    pre, cur = cur, t

Starting from slow.next (the beginning of the second half), we reverse the linked list using three pointers:

• pre: tracks the previous node (initially None)
• cur: the current node being processed
• t: temporarily stores the next node

The reversal works by:

1. Saving the next node in t
2. Pointing current node's next to the previous node
3. Moving pre and cur forward

After this loop, pre points to the head of the reversed second half.

Step 3: Compare Both Halves

while pre:
    if pre.val != head.val:
        return False
    pre, head = pre.next, head.next
return True

We traverse both halves simultaneously:

• head traverses the first half from the beginning
• pre traverses the reversed second half

If any values don't match, we return False. If we complete the traversal without mismatches, the list is a palindrome.

Time Complexity: O(n) - we traverse the list twice (once to find middle and reverse, once to compare)

Space Complexity: O(1) - only using a constant number of pointers, no additional data structures

Example Walkthrough

Let's walk through the solution with the linked list: 1 -> 2 -> 3 -> 2 -> 1

Initial State:

1 -> 2 -> 3 -> 2 -> 1 -> null

Step 1: Find the Middle

Initialize pointers:

• slow points to node 1 (head)
• fast points to node 2 (head.next)

Iteration 1:

• slow moves to node 2
• fast moves to node 3 (one step) then node 2 (second step)

Iteration 2:

• slow moves to node 3
• fast moves to node 1 (one step) then null (second step)
• Loop ends since fast.next is null

After finding middle:

1 -> 2 -> 3 -> 2 -> 1 -> null
          ^
        slow

Step 2: Reverse Second Half

Start reversing from slow.next (node 2):

Initial: pre = null, cur = node 2

Iteration 1:

• Save t = node 1
• Set node 2.next = null
• Move: pre = node 2, cur = node 1

Iteration 2:

• Save t = null
• Set node 1.next = node 2
• Move: pre = node 1, cur = null
• Loop ends

After reversal:

First half:  1 -> 2 -> 3
                       ↓
                      null

Second half: 1 -> 2 -> null
             ^
            pre

Step 3: Compare Both Halves

Start comparison with head at node 1 (first half) and pre at node 1 (reversed second half):

Iteration 1:

• Compare: node 1.val (1) == node 1.val (1) ✓
• Move both pointers forward

Iteration 2:

• Compare: node 2.val (2) == node 2.val (2) ✓
• Move both pointers forward

Iteration 3:

• pre becomes null
• Loop ends

All values matched, so return true - the linked list is a palindrome!

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the linked list.

The algorithm consists of three main phases:

1. Finding the middle of the linked list: The two-pointer technique (slow and fast pointers) traverses approximately half the list with the fast pointer and the full first half with the slow pointer. This takes O(n/2) time.
2. Reversing the second half: The second half of the list is reversed by iterating through approximately n/2 nodes. This takes O(n/2) time.
3. Comparing both halves: The comparison loop iterates through at most n/2 nodes to check if values match. This takes O(n/2) time.

Total time complexity: O(n/2) + O(n/2) + O(n/2) = O(3n/2) = O(n)

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space:

• A few pointer variables (slow, fast, pre, cur, t) are used regardless of the input size
• The linked list is modified in-place by reversing the second half
• No additional data structures (arrays, stacks, or new nodes) are created

The space usage remains constant regardless of the size of the input linked list, resulting in O(1) space complexity.

Common Pitfalls

1. Incorrect Fast Pointer Initialization

One of the most common mistakes is initializing both slow and fast pointers at head instead of setting fast = head.next. This causes the slow pointer to end up one position too far, leading to incorrect palindrome detection.

Incorrect approach:

slow = head
fast = head  # Wrong! Should be head.next
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

Why this fails: When both pointers start at the same position, for even-length lists, the slow pointer will be at the first node of the second half instead of the last node of the first half. This causes misalignment during comparison.

Example where it fails:

• List: 1 -> 2 -> 2 -> 1
• With incorrect initialization: slow ends at the second 2, causing comparison misalignment
• With correct initialization: slow ends at the first 2, properly dividing the list

Solution: Always initialize fast = head.next to ensure proper middle detection:

slow = head
fast = head.next  # Correct initialization

2. Not Handling Edge Cases

The code may fail for edge cases like:

• Single node lists (e.g., 1)
• Two-node lists (e.g., 1 -> 1)
• Empty lists (though typically the problem guarantees non-empty lists)

Potential issue: If head.next is None (single node), fast = head.next would be None, and the while loop wouldn't execute, leaving slow.next as None, which could cause issues.

Solution: Add edge case handling:

def isPalindrome(self, head: Optional[ListNode]) -> bool:
    # Handle single node case
    if not head or not head.next:
        return True
  
    # Continue with the regular algorithm...

3. Modifying the Original List Structure

The algorithm reverses the second half of the list in-place, which permanently modifies the original linked list structure. This might be problematic if the list needs to be preserved for other operations.

Impact: After checking for palindrome, the list structure is broken:

• Original: 1 -> 2 -> 3 -> 2 -> 1
• After algorithm: 1 -> 2 -> 3 <- 2 <- 1 (with 3.next still pointing to the old 2)

Solution: If preserving the original structure is required, reverse the second half back after comparison:

def isPalindrome(self, head: Optional[ListNode]) -> bool:
    # ... existing code to find middle and reverse ...
  
    # Store the head of reversed second half
    reversed_head = previous
  
    # Compare the halves
    first_half = head
    second_half = reversed_head
    result = True
  
    while second_half:
        if first_half.val != second_half.val:
            result = False
            break
        first_half = first_half.next
        second_half = second_half.next
  
    # Restore the original list structure
    previous = None
    current = reversed_head
    while current:
        temp = current.next
        current.next = previous
        previous = current
        current = temp
  
    # Reconnect the two halves
    slow.next = previous
  
    return result

4. Comparison Loop Boundary Issues

A subtle issue can occur if the comparison loop doesn't handle odd-length lists correctly. For odd-length lists, the middle element doesn't need to be compared with itself.

Example: For list 1 -> 2 -> 3 -> 2 -> 1:

• First half: 1 -> 2 -> 3
• Second half (reversed): 1 -> 2
• The middle element 3 shouldn't affect palindrome check

The current solution handles this correctly by only iterating while previous exists (the reversed second half is shorter for odd-length lists), but developers might mistakenly try to compare equal-length segments.