Palindrome Linked List

You are given the head of a singly linked list. Return true if the sequence of values stored in the list reads the same from front to back as from back to front, and false otherwise.

In the test cases a list is written as an array of its values in order, e.g. [3,8,8,3]; your function receives the head node.

Copying the values into an array makes this easy. Can you do it in O(n) time while using only O(1) extra memory?

Example 1

Example 2

Example 3

Constraints

• 1 <= number of nodes <= 105
• 0 <= Node.val <= 9

Pattern Path · Linked Lists · problem 70 of 169

Start simple

Copy all values into an array and compare it with its reverse (or use two indices): O(n) time but O(n) extra space.

The key idea

A palindrome check compares each value with its mirror image, which needs walking from both ends at once. A singly linked list can only go forward, so make the back half go forward too, by reversing it in place.

• Find the middle. Move slow one node and fast two nodes per step. When fast runs off the end, slow sits at the middle (the second middle for even lengths).
• Reverse from the middle. Standard pointer reversal turns the back half into a list that starts at the original tail.
• Compare. Walk from head and from the reversed half together. Any mismatch means not a palindrome. Stop when the reversed half ends; for odd lengths the middle node is compared with itself, which is harmless.

Each phase is a single linear pass and only a few pointers are kept, so memory stays constant. In production code you would reverse the half back afterwards so the caller's list is left unchanged.

Complexity

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

Python

class Solution:
    def isPalindrome(self, head):
        # 1. Find the middle: fast moves twice as quickly as slow.
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # 2. Reverse the second half, starting at the middle.
        prev = None
        while slow:
            nxt = slow.next
            slow.next = prev
            prev = slow
            slow = nxt

        # 3. Compare the first half with the reversed second half.
        left, right = head, prev
        while right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        return True

JavaScript

var isPalindrome = function(head) {
  // 1. Find the middle: fast moves twice as quickly as slow.
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  // 2. Reverse the second half, starting at the middle.
  let prev = null;
  while (slow) {
    const next = slow.next;
    slow.next = prev;
    prev = slow;
    slow = next;
  }

  // 3. Compare the first half with the reversed second half.
  let left = head, right = prev;
  while (right) {
    if (left.val !== right.val) return false;
    left = left.next;
    right = right.next;
  }
  return true;
};

What the interviewer is checking

It combines two core linked-list moves, the fast/slow middle finder and in-place reversal, and checks that you can compose them without losing nodes.

Mistakes to avoid

• Off-by-one errors in finding the middle for odd versus even lengths.
• Losing the rest of the list during reversal by overwriting next before saving it.
• A recursive solution that looks O(1) but actually uses O(n) call-stack space.
• Leaving the input mutated when the caller expects it intact (restore the half if required).

Follow-ups to expect

• How do you restore the original list afterwards? (Reverse the second half again.)
• Solve it recursively. (Front pointer advanced during unwinding; O(n) stack.)
• What if the list were doubly linked? (Walk inward from both ends.)

In real software

Reversing part of a linked structure in place is a common step in memory-tight systems code, such as kernels or embedded firmware, where allocating a copy is not an option.

Practice next