Palindrome Linked List Check

Problem Statement

Given the head of a singly linked list, return true if it reads the same forward and backward.

Example

Input:  1 -> 2 -> 2 -> 1
Output: true

Two Pointer Approach

Find the middle with fast/slow pointers, reverse the second half of the list, then walk the first half and the reversed half together comparing values. This achieves O(1) extra space.

Complexity

• Time: O(n)
• Space: O(1)

Solution Code

Python

def isPalindrome(head):
    slow = fast = head
    while fast and fast.next:          # find middle
        slow = slow.next
        fast = fast.next.next
    prev = None                        # reverse second half
    while slow:
        slow.next, prev, slow = prev, slow, slow.next
    left, right = head, prev           # compare halves
    while right:
        if left.val != right.val:
            return False
        left, right = left.next, right.next
    return True

Java

boolean isPalindrome(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
    ListNode prev = null;
    while (slow != null) { ListNode nxt = slow.next; slow.next = prev; prev = slow; slow = nxt; }
    ListNode left = head, right = prev;
    while (right != null) {
        if (left.val != right.val) return false;
        left = left.next; right = right.next;
    }
    return true;
}

C++

bool isPalindrome(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    ListNode* prev = nullptr;
    while (slow) { ListNode* nxt = slow->next; slow->next = prev; prev = slow; slow = nxt; }
    ListNode* left = head; ListNode* right = prev;
    while (right) {
        if (left->val != right->val) return false;
        left = left->next; right = right->next;
    }
    return true;
}

Key Takeaways

• Combines two classic patterns: find-middle and reverse-list.
• Comparing against the reversed half avoids an O(n) array copy.
• Optionally restore the list by reversing the half back.