LeetCode Solutions Blog

Palindrome Linked List

Number: 234

Difficulty: Easy

Paid? No

Problem Description

Given the head of a singly linked list, determine if the list is a palindrome. In other words, check whether the list reads the same backward as forward.

Key Insights

Use two pointers (slow and fast) to reach the middle of the list.
Reverse the second half of the list.
Compare the nodes from the start of the list to the reversed half.
This approach meets the O(n) time and O(1) space follow-up requirement.

Space and Time Complexity

Time Complexity: O(n) – each node is visited a constant number of times. Space Complexity: O(1) – only constant extra space is used (in-place reversal).

Solution

We first use the two-pointer technique to locate the midpoint of the linked list. The slow pointer moves one step at a time while the fast pointer moves two steps. Once the middle is found, we reverse the second half of the list in-place. Finally, we traverse both halves concurrently to compare the node values. If all corresponding values match, the linked list is a palindrome. A potential gotcha is handling the odd number of nodes; in that case, we ignore the middle element when comparing.

Code Solutions

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        # Find the midpoint using slow and fast pointers
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next          # Move slow pointer by 1
            fast = fast.next.next     # Move fast pointer by 2
        
        # Reverse the second half of the list
        prev = None
        while slow:
            next_node = slow.next     # Store the next node
            slow.next = prev          # Reverse the current node's pointer
            prev = slow               # Move prev to current node
            slow = next_node          # Move to next node
        
        # Compare the first half and the reversed second half node by node
        left, right = head, prev
        while right:                  # Only need to compare till the end of second half
            if left.val != right.val:
                return False        # Mismatch found, not a palindrome
            left = left.next        # Move left pointer
            right = right.next      # Move right pointer
        
        return True                 # All nodes matched, it's a palindrome