Domain 1EasyCORE

Palindrome Linked List

The problem asks us to determine if a singly linked list is a palindrome. A palindrome reads the same forwards and backwards. The input is the head of a singly linked list, and the output should be a boolean indicating whether the list is a palindrome or not.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Linked List#Two Pointers

234. Palindrome Linked List

Model: qwen2.5-coder:14b
Topics: Linked List,Two Pointers
FAANG asked: 1
Acceptance rate: 41.9%


Problem Breakdown

The problem asks us to determine if a singly linked list is a palindrome. A palindrome reads the same forwards and backwards. The input is the head of a singly linked list, and the output should be a boolean indicating whether the list is a palindrome or not.

Inputs:

  • head: The head node of a singly linked list.

Outputs:

  • A boolean value (true or false) indicating if the linked list is a palindrome.

Implicit Constraints/Edge Cases:

  • The list can have anywhere from 1 to 10^5 nodes.
  • Node values are integers between 0 and 9, inclusive.
  • Edge cases include:
    • A single-node list (which is trivially a palindrome).
    • An empty list (though the problem specifies at least one node, this could be an implicit consideration).

Intuition

A brute-force approach would involve converting the linked list into an array and then checking if the array is a palindrome. This approach has a time complexity of O(n) due to the traversal needed to convert the list to an array and another O(n) for checking the palindrome, resulting in O(2n) or simply O(n). However, it uses additional space proportional to the number of nodes (O(n)) because we store all node values in an array.

A more efficient approach is to use two pointers to find the middle of the linked list and then reverse the second half of the list. This allows us to compare the first half with the reversed second half directly, achieving O(n) time complexity and O(1) space complexity.

Approach

  1. Find the Middle of the List: Use the slow and fast pointer technique where one pointer moves twice as fast as the other. When the fast pointer reaches the end, the slow pointer will be at the middle.
  2. Reverse the Second Half: Starting from the middle, reverse the second half of the list.
  3. Compare the Two Halves: Compare the values of nodes in the first half with the reversed second half.
  4. Restore the List (Optional): If needed, restore the original list by reversing the second half again.
  5. Return Result: Return true if all corresponding nodes match; otherwise, return false.

Complexity Analysis

  • Time Complexity: O(n) because we traverse the list a constant number of times (to find the middle, reverse the second half, and compare).
  • Space Complexity: O(1) as we only use a few extra pointers regardless of the input size.

Solution

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

def isPalindrome(head: ListNode) -> bool:
    # Step 1: Find the middle of the list using slow and fast pointers
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    # Step 2: Reverse the second half of the list
    prev = None
    while slow:
        next_node = slow.next
        slow.next = prev
        prev = slow
        slow = next_node
    
    # Step 3: Compare the first half and the reversed second half
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next
    
    # Step 4: Restore the list (optional)
    # Reverse the second half again to restore the original list structure
    prev = None
    while prev is not head:
        next_node = head.next
        head.next = prev
        prev = head
        head = next_node
    
    return True

Edge Cases Handled

  • Single Node: The list is trivially a palindrome.
  • Two Nodes: Compares the two nodes directly.
  • Odd Length List: The middle node is ignored in comparison.
  • Even Length List: Both halves are of equal length and compared directly.