Check if a Linked list is a Palindrome or Not

Write code that will check if a linked list is a palindrome or not.

💡Strategies for Solving This Problem

The Problem

I got this question at Meta and initially froze. A palindrome linked list reads the same forwards and backwards: 1→2→2→1 is a palindrome, 1→2→3 isn't. The tricky part? You can't just index backwards like with an array.

Approach 1: Reverse and Compare (What I Used)

The insight: if the list is a palindrome, the first half equals the reversed second half.

Find the middle using slow/fast pointers
Reverse the second half
Compare first half with reversed second half

My interviewer at Meta specifically said "You can modify the list." That's your hint to use this approach.

Approach 2: Using a Stack

Push first half onto a stack, then compare with second half as you pop. Simpler to implement but uses O(n) extra space. If interviewer says "optimize space," this won't fly.

Approach 3: Recursive (Elegant but Risky)

Use recursion to compare outer nodes working inward. Looks cool on paper but uses O(n) call stack space. I wouldn't use this in an interview unless you have time to kill.

Time Complexity

Reverse approach: O(n) time, O(1) space - this is what they want
Stack approach: O(n) time, O(n) space
Recursive: O(n) time, O(n) space (call stack)

Pro tip: Start by asking "Can I modify the original list?" This tells you which approach to use.

✅Solution

Solution: Fast/Slow Pointer + Reverse

class ListNode {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

function isPalindrome(head) {
    if (!head || !head.next) return true;

    // Step 1: Find middle using slow/fast pointers
    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // slow is now at the middle
    // Step 2: Reverse second half
    let secondHalf = reverseList(slow);

    // Step 3: Compare first and second half
    let firstHalf = head;
    while (secondHalf) {
        if (firstHalf.val !== secondHalf.val) {
            return false;
        }
        firstHalf = firstHalf.next;
        secondHalf = secondHalf.next;
    }

    return true;
}

function reverseList(head) {
    let prev = null;
    let current = head;

    while (current) {
        let next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }

    return prev;
}

// Test cases
// Create list: 1->2->2->1
let head1 = new ListNode(1);
head1.next = new ListNode(2);
head1.next.next = new ListNode(2);
head1.next.next.next = new ListNode(1);

console.log(isPalindrome(head1));  // true

// Create list: 1->2->3
let head2 = new ListNode(1);
head2.next = new ListNode(2);
head2.next.next = new ListNode(3);

console.log(isPalindrome(head2));  // false

Why This Works

Finding middle: Fast pointer moves 2x speed, so when it reaches the end, slow is at the middle
Reversing: We reverse the second half in-place (that's the O(1) space)
Comparing: Walk through both halves - if all values match, it's a palindrome

Edge Cases I Missed (and my interviewer caught)

Empty list: Return true (vacuously a palindrome)
Single node: Return true
Odd length: The extra middle node doesn't matter, algorithm still works

Alternative: Stack Approach (Easier to Code)

function isPalindromeStack(head) {
    let stack = [];
    let slow = head;
    let fast = head;

    // Push first half onto stack
    while (fast && fast.next) {
        stack.push(slow.val);
        slow = slow.next;
        fast = fast.next.next;
    }

    // If odd length, skip middle
    if (fast) slow = slow.next;

    // Compare second half with stack
    while (slow) {
        if (stack.pop() !== slow.val) {
            return false;
        }
        slow = slow.next;
    }

    return true;
}

This is cleaner code but uses O(n) space. My interviewer asked me to optimize space - that's when I switched to the reverse approach.

Complexity

Time: O(n) - single pass to find middle, O(n/2) to reverse, O(n/2) to compare
Space: O(1) - only pointer variables, no extra data structures

Interview tip: Code the stack solution first (it's easier). Then if interviewer asks for space optimization, explain the reverse approach.