Palindrome Linked List: A Clean & Simple Visual Guide

The Core Problem

A palindrome is a sequence that reads exactly the same forwards and backwards (like the word "racecar"). Your goal is to determine if a singly linked list meets this exact criteria.

Example 1:

Input: head = [1, 2, 2, 1]

Output: true

Example 2:

Input: head = [1, 2]

Output: false

The naive approach is to loop through the linked list, copy all the values into a standard Array or List, and then check if that array is symmetrical. While this works and solves the problem in O(n) time, it requires O(n) extra memory to store the array.

The true challenge is: Can you do this in O(1) constant space? (Without creating any new arrays or data structures).

Interactive Visualization

To achieve O(1) space, we must modify the linked list in place. Use the interactive tool below to step through the elegant three-phase algorithm that makes this possible without extra memory.

Fast & Slow Pointers (The Optimal Approach)

To check for symmetry without extra space, we need to compare the first half of the list to the reversed second half of the list.

Here is a real-world analogy:

Imagine a long freight train. You want to know if the front half of the train looks identical to the back half.

Find the Middle: You send two inspectors walking down the train. One walks normally (Slow pointer), and one sprints at twice the speed (Fast pointer). When the sprinter hits the end of the train, the slow walker is standing exactly in the middle.

Flip the Back Half: Starting from the middle, you manually turn every train car in the second half around so they face backwards.

Compare: One inspector starts at the very front of the train, and the other starts at the newly reversed back of the train. They walk inwards, comparing cars one by one. If they all match, the train is a palindrome!

Code Implementations

Here is the production-ready code that executes this three-phase strategy perfectly.

TypeScript / JavaScript

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val===undefined ? 0 : val);
        this.next = (next===undefined ? null : next);
    }
}

function isPalindrome(head: ListNode | null): boolean {
    if (!head || !head.next) return true;

    // Phase 1: Find the middle using Fast & Slow pointers
    let slow: ListNode | null = head;
    let fast: ListNode | null = head;
    
    while (fast !== null && fast.next !== null) {
        slow = slow.next!;
        fast = fast.next.next;
    }

    // Phase 2: Reverse the second half of the list
    let prev: ListNode | null = null;
    let curr: ListNode | null = slow;
    
    while (curr !== null) {
        let nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }

    // Phase 3: Compare the first half and the reversed second half
    let p1: ListNode | null = head;
    let p2: ListNode | null = prev;
    
    while (p2 !== null) {
        if (p1!.val !== p2.val) {
            return false;
        }
        p1 = p1!.next;
        p2 = p2.next;
    }

    return true;
}

Python 3

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

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return True
            
        # Phase 1: Find the middle
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
        # Phase 2: Reverse the second half
        prev = None
        curr = slow
        while curr:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
            
        # Phase 3: Compare halves
        p1 = head
        p2 = prev
        while p2:
            if p1.val != p2.val:
                return False
            p1 = p1.next
            p2 = p2.next
            
        return True

Java

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;

        // Phase 1: Find the middle
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Phase 2: Reverse the second half
        ListNode prev = null, curr = slow;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }

        // Phase 3: Compare halves
        ListNode p1 = head, p2 = prev;
        while (p2 != null) {
            if (p1.val != p2.val) {
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        return true;
    }
}

Complexity Analysis

Time Complexity: O(N)

We make exactly two passes over the list. Finding the middle takes O(N/2) time, reversing the second half takes O(N/2) time, and comparing the halves takes another O(N/2) time. This simplifies to an overall linear time complexity of O(N).

Space Complexity: O(1)

Because we manipulate the .next pointers of the existing list nodes directly in memory, we do not allocate any additional data structures (like arrays or stacks). This achieves strictly constant extra space.

Summary & Key Takeaways

• To solve linked list symmetry problems without extra memory, you must modify the list in-place.
• The Fast and Slow pointer technique is the gold standard for finding the middle of a linked list in a single pass.
• In production environments, it is often best practice to add a "Phase 4" that reverses the second half back to its original state so that you don't permanently destroy the structure of the input data.

Academic Callout: Mastering foundational data structure manipulations like list reversals and multi-pointer traversal ensures your code is robust. Ensure your academic tracking is just as robust by utilizing the free AnaCGPA Calculator Tools to seamlessly convert and calculate your grades.