Palindrome Linked List

# Definition of a ListNode
class ListNode:
  def __init__(self, value=0, next=None):
    self.value = value
    self.next = next

True

left-to-right:  5 -> 4 -> 3 -> 4 -> 5
right-to-left: 5 -> 4 -> 3 -> 4 -> 5   

False

left-to-right:  5 -> 4 -> 3
right-to-left: 3 -> 4 -> 5

// class ListNode {
//     int val;
//     ListNode next;
// }

public class Solution {
    public Boolean isPalindrome(ListNode head) {
        // Your code goes here
    }
}

Solutions

To determine if a linked list is a palindrome, we need to compare the values of the nodes when read from left-to-right and right-to-left. But since our linked list is singly linked, we can only read its values from left-to-right.

One way around this problem is to convert the linked list to a list, which supports reading values from both directions.

1. Convert to List: Compare Reverse

If we convert the original linked list to a list, we can compare the list with its reverse to determine if it is a palindrome. If the list is a palindrome, the list and its reverse will be equal.

public boolean isPalindrome(ListNode head) {
    // convert linked list to list
    List<Integer> vals = new ArrayList<>();
    ListNode currentNode = head;
    while (currentNode != null) {
        vals.add(currentNode.val);
        currentNode = currentNode.next;
    }
    
    // compare list with its reverse
    List<Integer> reversed = new ArrayList<>(vals);
    Collections.reverse(reversed);
    return vals.equals(reversed);
}

Time Complexity: O(n) where n is the number of nodes in the linked list. We iterate through each node in the linked list once to convert it to a list and then compare the list with its reverse, both of which are O(n) operations.

Space Complexity: O(n) where n is the number of nodes in the linked list, because we store the values of each node in a list.

2. Convert to List: Two-Pointer Technique

Instead of comparing the entire list with its reverse, we can use the two-pointer technique to check if the values in the list are a palindrome.

Like the previous solution, we first traverse the linked list and store the value of each node in a list.

Then, we initialize two pointers, left and right, at the start and end of the list, respectively. We compare the values at the left and right pointers. If they are equal, we move them both towards the center of the list. If the values at the left and right pointers are not equal, the list is not a palindrome.

public boolean isPalindrome(ListNode head) {
    // convert linked list to list
    List<Integer> vals = new ArrayList<>();
    ListNode current = head;
    while (current != null) {
        vals.add(current.val);
        current = current.next;
    }
    
    int left = 0, right = vals.size() - 1;
    while (left < right) {
        if (!vals.get(left).equals(vals.get(right))) {
            return false;
        }
        left++;
        right--;
    }
    
    return true;
}

Time Complexity: O(n) where n is the number of nodes in the linked list. We iterate through each node in the linked list once to convert it to a list and then compare the values at the left and right pointers, which is also an O(n) operation. This is a slightly more time efficient solution than the previous one because we can stop as soon as we find a pair of values that are not equal during the palindrome check.

Space Complexity: O(n) where n is the number of nodes in the linked list. Like the previous solution, we store the values of each node in a list. This is also a slightly more space efficient solution than the previous one because we don't have to store the entire reverse of the list to compare it with the original.

3. Optimal Solution: Reverse Second Half

In the two-pointer above approach, we compared the first half of the list with the second half of the list, in reverse.

So if we first modify our linked list by reversing the direction of the nodes in the second half of the list, we can solve this problem without having to first convert the linked list to a list. This is the optimal solution, with a time complexity of O(n) and space complexity of O(1).

Step 1: Find the Middle of the Linked List

This step can be done using fast and slow pointers, which involves initializing two pointers, fast and slow, at the head of the linked list, and then iterating until fast reaches the end of the list. At each iteration, slow moves one node forward and fast moves two nodes forward. When fast reaches the tail node of the list, slow will point to the middle node in the list.

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) {
        return true;
    }
    
    // find middle node
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    
    // reverse second half
    ListNode prev = null;
    while (slow != null) {
        ListNode next = slow.next;
        slow.next = prev;
        prev = slow;
        slow = next;
    }
    
    // compare halves
    ListNode first = head, second = prev;
    while (second != null) {
        if (first.val != second.val) {
            return false;
        }
        first = first.next;
        second = second.next;
    }
    
    return true;
}

When there are an even number of nodes, fast will equal to None after moving past the tail node, and slow will be the first node of the second half of the list. In the case below, there are 4 nodes, so slow will point to the 3rd node.

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) {
        return true;
    }
    
    // find middle node
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    
    // reverse second half
    ListNode prev = null;
    while (slow != null) {
        ListNode next = slow.next;
        slow.next = prev;
        prev = slow;
        slow = next;
    }
    
    // compare halves
    ListNode first = head, second = prev;
    while (second != null) {
        if (first.val != second.val) {
            return false;
        }
        first = first.next;
        second = second.next;
    }
    
    return true;
}

Step 2: Reverse second half of list

At this point, slow points to the middle node in the list. Next, we want to reverse the direction of the pointers of each node starting from slow to the tail of the list.

Reversing the nodes in a linked list is a common problem that can be solved by iterating over each node that needs to be reversed. The key idea is to maintain three pointers, prev, curr, and next_, where prev points to the previous node, curr points to the node with the pointer we want to reverse, and next_ points to the next node in the iteration.

At each iteration, we:

• save the next node in the iteration by setting next_ = curr.next
• reverse the pointer by setting curr.next = prev
• move pointers for the next iteration by set curr = next_ and prev = curr

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) {
        return true;
    }
    
    // find middle node
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    
    // reverse second half
    ListNode prev = null;
    while (slow != null) {
        ListNode next = slow.next;
        slow.next = prev;
        prev = slow;
        slow = next;
    }
    
    // compare halves
    ListNode first = head, second = prev;
    while (second != null) {
        if (first.val != second.val) {
            return false;
        }
        first = first.next;
        second = second.next;
    }
    
    return true;
}

Step 3: Check for Palindrome

With the nodes reversed, we can now use two pointers to compare the values of the nodes in the first half of the list with the reversed second half of the list.

At this point, prev points to the head of the reversed second half of the list. We can set a pointer left equal to the head of the original list and right equal to prev.

We then iterate through the list, comparing the values at left and right. If the values are not equal, the list is not a palindrome. If they are equal, we move left and right towards the center of the list, until they meet at the same node, at which point we return True because our list is a palindrome.

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) {
        return true;
    }
    
    // find middle node
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    
    // reverse second half
    ListNode prev = null;
    while (slow != null) {
        ListNode next = slow.next;
        slow.next = prev;
        prev = slow;
        slow = next;
    }
    
    // compare halves
    ListNode first = head, second = prev;
    while (second != null) {
        if (first.val != second.val) {
            return false;
        }
        first = first.next;
        second = second.next;
    }
    
    return true;
}

Detecting the list is not a palindrome:

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) {
        return true;
    }
    
    // find middle node
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    
    // reverse second half
    ListNode prev = null;
    while (slow != null) {
        ListNode next = slow.next;
        slow.next = prev;
        prev = slow;
        slow = next;
    }
    
    // compare halves
    ListNode first = head, second = prev;
    while (second != null) {
        if (first.val != second.val) {
            return false;
        }
        first = first.next;
        second = second.next;
    }
    
    return true;
}

To recap:

1. Find the middle of the linked list using the fast and slow pointers technique.
2. Reverse the direction of the nodes in the second half of the linked list.
3. Use two-pointers to check for a palindrome by comparing the values of the nodes in the first half of the list with the reversed second half of the list.

Implementation

Here's the complete optimal solution that implements the three-step approach:

public boolean isPalindrome(ListNode head) {
    // Find middle of the linked list using fast and slow pointers
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    // Reverse second half of the list
    ListNode prev = null;
    while (slow != null) {
        ListNode next = slow.next;  // Save next node
        slow.next = prev;           // Reverse pointer
        prev = slow;                // Move pointers
        slow = next;
    }
    // Check palindrome by comparing halves
    ListNode first = head, second = prev;
    while (second != null) {
        if (first.val != second.val) {
            return false;
        }
        first = first.next;
        second = second.next;
    }
    return true;
}

Code

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) {
        return true;
    }
    
    // find middle node
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    
    // reverse second half
    ListNode prev = null;
    while (slow != null) {
        ListNode next = slow.next;
        slow.next = prev;
        prev = slow;
        slow = next;
    }
    
    // compare halves
    ListNode first = head, second = prev;
    while (second != null) {
        if (first.val != second.val) {
            return false;
        }
        first = first.next;
        second = second.next;
    }
    
    return true;
}

Edge Cases

Empty List

When the linked list is empty, all of the pointers will be None, and the function returns True immediately because an empty list is a palindrome.

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) {
        return true;
    }
    
    // find middle node
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    
    // reverse second half
    ListNode prev = null;
    while (slow != null) {
        ListNode next = slow.next;
        slow.next = prev;
        prev = slow;
        slow = next;
    }
    
    // compare halves
    ListNode first = head, second = prev;
    while (second != null) {
        if (first.val != second.val) {
            return false;
        }
        first = first.next;
        second = second.next;
    }
    
    return true;
}

Single Node

When the linked list has a single node:

1. fast.next is None, so the first while loop to find the middle node doesn't execute.
2. Reversing the second half of the list has no effect because there is only one node.
3. The palindrome check returns True because a single node is a palindrome.

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) {
        return true;
    }
    
    // find middle node
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    
    // reverse second half
    ListNode prev = null;
    while (slow != null) {
        ListNode next = slow.next;
        slow.next = prev;
        prev = slow;
        slow = next;
    }
    
    // compare halves
    ListNode first = head, second = prev;
    while (second != null) {
        if (first.val != second.val) {
            return false;
        }
        first = first.next;
        second = second.next;
    }
    
    return true;
}

Two Nodes (Palindrome)

When the linked list has two nodes:

1. The first while loop sets the slow pointer to the second node.
2. Reversing the second half of the list has no effect slow.next is None already.
3. The palindrome check compares the values of the two nodes and returns True if they are equal.

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) {
        return true;
    }
    
    // find middle node
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    
    // reverse second half
    ListNode prev = null;
    while (slow != null) {
        ListNode next = slow.next;
        slow.next = prev;
        prev = slow;
        slow = next;
    }
    
    // compare halves
    ListNode first = head, second = prev;
    while (second != null) {
        if (first.val != second.val) {
            return false;
        }
        first = first.next;
        second = second.next;
    }
    
    return true;
}

Two Nodes (Not Palindrome)

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) {
        return true;
    }
    
    // find middle node
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    
    // reverse second half
    ListNode prev = null;
    while (slow != null) {
        ListNode next = slow.next;
        slow.next = prev;
        prev = slow;
        slow = next;
    }
    
    // compare halves
    ListNode first = head, second = prev;
    while (second != null) {
        if (first.val != second.val) {
            return false;
        }
        first = first.next;
        second = second.next;
    }
    
    return true;
}

Trade-off: The O(1) space solution mutates the input

The O(1) space solution comes with a significant practical downside: it mutates the input linked list. During execution, the second half of the list is reversed in-place, which means any other code holding a reference to nodes in that portion of the list will see a corrupted structure while the check is running.

You could reverse the second half again after the palindrome check to restore the original list, but that's additional O(n) work and still isn't safe in concurrent or multi-threaded contexts where another thread might read the list mid-mutation.

In real-world code, mutating an input data structure passed to a read-only query function like isPalindrome is almost always unacceptable. If you need to avoid mutation, you're back to O(n) space — whether that's copying the list, collecting values into an array, or using a stack. The array-based solutions (Solutions 1 and 2 above) are typically the better choice in practice for this reason.

The O(1) space approach is worth knowing because interviewers often ask for it specifically, and it demonstrates important linked list manipulation techniques (fast/slow pointers, in-place reversal). Just be ready to discuss why you might not use it in production.