Palindrome linked list

"Given a linked list, check if it's a palindrome using constant space." This classic Palindrome Linked List problem is a favorite at companies like Amazon, Microsoft, and Adobe because it tests two fundamental linked list techniques at once: the slow/fast pointer trick and in-place list reversal. If you can combine both cleanly, you can handle most linked list problems thrown at you in an interview.

TL;DR

Find the middle of the list using slow and fast pointers. Reverse the second half in-place. Walk both halves simultaneously, comparing node values. If every pair matches, it's a palindrome. Three helper concepts, zero extra space.

Why This Problem Matters

Palindrome checking on arrays is straightforward since you have random access. Linked lists force you to think differently because you can only walk forward. This problem teaches you how to overcome that limitation by combining two essential patterns: finding the midpoint without knowing the length, and reversing a sublist in constant space. These same techniques appear in dozens of other linked list problems, from reordering lists to detecting cycles.

Understanding the Problem

Given the head of a singly linked list, determine whether the values form a palindrome. The list [1, 3, 3, 1] is a palindrome because it reads the same in both directions. The list [1, 2] is not.

isPalindrome([1, 2, 2, 1]) -> true
isPalindrome([1, 2, 1])    -> true
isPalindrome([1, 2])       -> false
isPalindrome([0])          -> true
isPalindrome([])           -> true

The constraint is O(1) space. No copying values into an array. No stack. You are allowed to modify the list itself.

Edge Cases

1. Empty list (null head): Treated as a palindrome per the problem constraints
2. Single node [0]: Always a palindrome
3. Two identical nodes [1, 1]: A palindrome
4. Two different nodes [1, 2]: Not a palindrome
5. Odd-length palindrome [1, 2, 1]: The middle element is its own mirror

Solution Approach

The algorithm has three phases: find the middle, reverse the second half, and compare both halves.

Phase 1: Find the Middle

Use the slow and fast pointer technique. Slow advances one node at a time, fast advances two. When fast reaches the end, slow is at the middle.

For the list [1, 3, 3, 1]:

When fast becomes null, slow is sitting on the second 3 at index 2. That is the start of the second half.

Phase 2: Reverse the Second Half

Starting from the middle node, reverse the second half in-place using the standard three-pointer technique. For [1, 3, 3, 1], the second half [3, 1] becomes [1, 3].

Phase 3: Compare Both Halves

Walk two pointers simultaneously: one from the head of the original list, one from the head of the reversed second half. Compare values at each position.

Every pair matches, so the list is a palindrome.

When It Fails

For a non-palindrome like [1, 2, 3], the comparison catches the mismatch immediately:

Odd-Length Lists

Odd-length lists work naturally. For [1, 2, 1], the middle element gets included in the reversed half and compared against itself:

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public Boolean isPalindrome(ListNode head) {
    ListNode middleNode = getMiddle(head);
    ListNode reversedListHead = reverseList(middleNode);
    ListNode forwardListHead = head;

    while (forwardListHead != null && reversedListHead != null) {
      if (forwardListHead.data != reversedListHead.data) return false;
      forwardListHead = forwardListHead.next;
      reversedListHead = reversedListHead.next;
    }
    return true;
  }

  private ListNode reverseList(ListNode head) {
    ListNode iterator = head, previous = null;
    while (iterator != null) {
      ListNode nextNode = iterator.next;
      iterator.next = previous;
      previous = iterator;
      iterator = nextNode;
    }
    return previous;
  }

  private ListNode getMiddle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
    }
    return slow;
  }
}

The solution breaks down into three clean methods:

1. getMiddle: The slow/fast pointer loop. When fast can no longer advance two steps, slow is at the midpoint.
2. reverseList: Standard iterative reversal. Walk through the list, flipping each next pointer to point backward. Always save iterator.next in a temporary variable before overwriting it.
3. isPalindrome: Orchestrates the three phases. Find middle, reverse, compare.

Complexity Analysis

Time: O(n). Each phase traverses part or all of the list once. Finding the middle visits n/2 nodes, reversing visits n/2 nodes, and comparison visits at most n/2 nodes. The total is roughly 1.5n, which is O(n).

Space: O(1). We use a fixed number of pointer variables (slow, fast, iterator, previous, forwardListHead, reversedListHead) regardless of list size. No arrays, stacks, or recursion.

Common Pitfalls

1. Forgetting the empty list case: When head is null, getMiddle returns null, reverseList returns null, and the comparison loop never executes. The method correctly returns true. Make sure your implementation handles this gracefully.

2. Off-by-one in the middle: For even-length lists like [1, 2, 2, 1], slow ends up at index 2. For odd-length lists like [1, 2, 1], slow ends up at index 1. Both cases work because we compare from the head forward and from the reversed tail backward, and the halves align naturally.

3. Botching the reversal: The most common reversal bug is forgetting to save iterator.next before overwriting it. Always stash the next pointer in a temporary variable first.

4. Assuming the list is unchanged: The algorithm modifies the list by reversing the second half. If an interviewer asks about preserving the original structure, mention that you can reverse the second half again after comparison.

Interview Tips

When presenting this solution:

• Start by explaining the three-phase strategy before writing any code. "I'll find the middle, reverse the second half, then compare both halves."
• Mention that you know about the O(n) space alternatives (stack, recursion, copying to array) and explain why you chose the O(1) approach.
• If asked about restoring the list, explain that you could reverse the second half again after comparing. This shows awareness of side effects without complicating the initial solution.
• Draw the list state after each phase for a small example like [1, 2, 2, 1]. Interviewers appreciate seeing you trace through the algorithm visually.

Key Takeaways

• The palindrome linked list problem combines two building blocks: finding the middle (slow/fast pointers) and reversing a linked list (three-pointer technique). Mastering each independently makes this problem straightforward assembly.
• Reversing the second half in-place is the key to achieving O(1) space. No arrays, stacks, or other auxiliary data structures required.
• The algorithm naturally handles both odd-length and even-length lists because the comparison terminates when either pointer reaches null.
• Always mention the tradeoff between the O(n) space approach (copy to array) and the O(1) space approach (in-place reversal) to demonstrate engineering judgment in interviews.

Practice and Related Problems

Once you have palindrome linked list down, try these related challenges:

• Reverse a linked list (the core subroutine used here)
• Detect a cycle in a linked list (same slow/fast pointer pattern)
• Reorder list (combines midpoint finding with reversal and merging)

This problem and hundreds of others are available on Firecode, where spaced repetition ensures you internalize patterns like slow/fast pointers and in-place reversal rather than just memorizing solutions. Building fluency with these linked list primitives pays dividends across your entire interview preparation.

Solutions in Other Languages

Python

class Solution:
    def is_palindrome(self, head):
        middle_node = self.get_middle(head)
        reversed_list_head = self.reverse_list(middle_node)
        forward_list_head = head

        while forward_list_head is not None and reversed_list_head is not None:
            if forward_list_head.data != reversed_list_head.data:
                return False
            forward_list_head = forward_list_head.next
            reversed_list_head = reversed_list_head.next
        return True

    def reverse_list(self, head):
        iterator, previous = head, None
        while iterator is not None:
            next_node = iterator.next
            iterator.next = previous
            previous = iterator
            iterator = next_node
        return previous

    def get_middle(self, head):
        slow, fast = head, head
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
        return slow

JavaScript

class Solution {
  isPalindrome(head) {
    const middleNode = this.getMiddle(head);
    let reversedListHead = this.reverseList(middleNode);
    let forwardListHead = head;

    while (forwardListHead !== null && reversedListHead !== null) {
      if (forwardListHead.data !== reversedListHead.data) return false;
      forwardListHead = forwardListHead.next;
      reversedListHead = reversedListHead.next;
    }
    return true;
  }

  reverseList(head) {
    let iterator = head, previous = null;
    while (iterator !== null) {
      const nextNode = iterator.next;
      iterator.next = previous;
      previous = iterator;
      iterator = nextNode;
    }
    return previous;
  }

  getMiddle(head) {
    let slow = head;
    let fast = head;
    while (fast !== null && fast.next !== null) {
      slow = slow.next;
      fast = fast.next.next;
    }
    return slow;
  }
}

TypeScript

class Solution {
  isPalindrome(head: ListNode | null): boolean {
    const middleNode = this.getMiddle(head);
    let reversedListHead = this.reverseList(middleNode);
    let forwardListHead = head;

    while (forwardListHead !== null && reversedListHead !== null) {
      if (forwardListHead.data !== reversedListHead.data) return false;
      forwardListHead = forwardListHead.next;
      reversedListHead = reversedListHead.next;
    }
    return true;
  }

  private reverseList(head: ListNode | null): ListNode | null {
    let iterator = head;
    let previous: ListNode | null = null;
    while (iterator !== null) {
      const nextNode = iterator.next;
      iterator.next = previous;
      previous = iterator;
      iterator = nextNode;
    }
    return previous;
  }

  private getMiddle(head: ListNode | null): ListNode | null {
    let slow = head;
    let fast = head;
    while (fast !== null && fast.next !== null) {
      slow = slow!.next;
      fast = fast.next.next;
    }
    return slow;
  }
}

C++

class Solution {
public:
  bool isPalindrome(ListNode *head) {
    ListNode *middleNode = getMiddle(head);
    ListNode *reversedListHead = reverseList(middleNode);
    ListNode *forwardListHead = head;

    while (forwardListHead != nullptr && reversedListHead != nullptr) {
      if (forwardListHead->data != reversedListHead->data) return false;
      forwardListHead = forwardListHead->next;
      reversedListHead = reversedListHead->next;
    }
    return true;
  }

private:
  ListNode *reverseList(ListNode *head) {
    ListNode *iterator = head, *previous = nullptr;
    while (iterator != nullptr) {
      ListNode *nextNode = iterator->next;
      iterator->next = previous;
      previous = iterator;
      iterator = nextNode;
    }
    return previous;
  }

  ListNode *getMiddle(ListNode *head) {
    ListNode *slow = head;
    ListNode *fast = head;
    while (fast != nullptr && fast->next != nullptr) {
      slow = slow->next;
      fast = fast->next->next;
    }
    return slow;
  }
};

Go

package solution

func (s *Solution) IsPalindrome(head *ListNode) bool {
	middleNode := getMiddle(head)
	reversedListHead := reverseList(middleNode)
	forwardListHead := head

	for forwardListHead != nil && reversedListHead != nil {
		if forwardListHead.Data != reversedListHead.Data {
			return false
		}
		forwardListHead = forwardListHead.Next
		reversedListHead = reversedListHead.Next
	}
	return true
}

func reverseList(head *ListNode) *ListNode {
	var iterator, previous *ListNode = head, nil
	for iterator != nil {
		nextNode := iterator.Next
		iterator.Next = previous
		previous = iterator
		iterator = nextNode
	}
	return previous
}

func getMiddle(head *ListNode) *ListNode {
	slow := head
	fast := head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}

Scala

class Solution {
  def isPalindrome(head: ListNode): Boolean = {
    val middleNode = getMiddle(head)
    var reversedListHead = reverseList(middleNode)
    var forwardListHead = head

    while (forwardListHead != null && reversedListHead != null) {
      if (forwardListHead.data != reversedListHead.data) return false
      forwardListHead = forwardListHead.next
      reversedListHead = reversedListHead.next
    }
    true
  }

  private def reverseList(head: ListNode): ListNode = {
    var iterator = head
    var previous: ListNode = null
    while (iterator != null) {
      val nextNode = iterator.next
      iterator.next = previous
      previous = iterator
      iterator = nextNode
    }
    previous
  }

  private def getMiddle(head: ListNode): ListNode = {
    var slow = head
    var fast = head
    while (fast != null && fast.next != null) {
      slow = slow.next
      fast = fast.next.next
    }
    slow
  }
}

Kotlin

class Solution {
  fun isPalindrome(head: ListNode?): Boolean {
    val middleNode = getMiddle(head)
    var reversedListHead = reverseList(middleNode)
    var forwardListHead = head

    while (forwardListHead != null && reversedListHead != null) {
      if (forwardListHead.data != reversedListHead.data) return false
      forwardListHead = forwardListHead.next
      reversedListHead = reversedListHead.next
    }
    return true
  }

  private fun reverseList(head: ListNode?): ListNode? {
    var iterator = head
    var previous: ListNode? = null
    while (iterator != null) {
      val nextNode = iterator.next
      iterator.next = previous
      previous = iterator
      iterator = nextNode
    }
    return previous
  }

  private fun getMiddle(head: ListNode?): ListNode? {
    var slow = head
    var fast = head
    while (fast != null && fast.next != null) {
      slow = slow?.next
      fast = fast.next?.next
    }
    return slow
  }
}

Swift

class Solution {
    func isPalindrome(_ head: ListNode?) -> Bool {
        let middleNode = getMiddle(head)
        var reversedListHead = reverseList(middleNode)
        var forwardListHead = head

        while forwardListHead != nil && reversedListHead != nil {
            if forwardListHead!.data != reversedListHead!.data { return false }
            forwardListHead = forwardListHead!.next
            reversedListHead = reversedListHead!.next
        }
        return true
    }

    private func reverseList(_ head: ListNode?) -> ListNode? {
        var iterator = head
        var previous: ListNode? = nil
        while iterator != nil {
            let nextNode = iterator!.next
            iterator!.next = previous
            previous = iterator
            iterator = nextNode
        }
        return previous
    }

    private func getMiddle(_ head: ListNode?) -> ListNode? {
        var slow = head
        var fast = head
        while fast != nil && fast!.next != nil {
            slow = slow!.next
            fast = fast!.next!.next
        }
        return slow
    }
}

Rust

impl Solution {
    pub fn is_palindrome(&self, head: Option<Box<ListNode>>) -> bool {
        let (first_half, second_half) = Self::split_at_middle(head);
        let mut reversed_head = Self::reverse_list(second_half);
        let mut forward_head = first_half;

        while let (Some(forward_node), Some(reversed_node)) = (&forward_head, &reversed_head) {
            if forward_node.data != reversed_node.data {
                return false;
            }
            forward_head = forward_head.unwrap().next;
            reversed_head = reversed_head.unwrap().next;
        }
        true
    }

    fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut previous: Option<Box<ListNode>> = None;
        let mut current = head;
        while let Some(mut node) = current {
            let next_node = node.next.take();
            node.next = previous;
            previous = Some(node);
            current = next_node;
        }
        previous
    }

    fn split_at_middle(
        head: Option<Box<ListNode>>,
    ) -> (Option<Box<ListNode>>, Option<Box<ListNode>>) {
        if head.is_none() {
            return (None, None);
        }
        let mut length = 0;
        let mut current = &head;
        while let Some(node) = current {
            length += 1;
            current = &node.next;
        }
        let mid = length / 2;
        let mut current = head;
        let mut first_head: Option<Box<ListNode>> = None;
        let mut first_tail: *mut Option<Box<ListNode>> = &mut first_head;
        for _ in 0..mid {
            if let Some(mut node) = current {
                current = node.next.take();
                unsafe {
                    *first_tail = Some(node);
                    first_tail = &mut (*first_tail).as_mut().unwrap().next;
                }
            }
        }
        (first_head, current)
    }
}

C#

public class Solution {
    public bool isPalindrome(ListNode? head) {
        ListNode? middleNode = GetMiddle(head);
        ListNode? reversedListHead = ReverseList(middleNode);
        ListNode? forwardListHead = head;

        while (forwardListHead != null && reversedListHead != null) {
            if (forwardListHead.data != reversedListHead.data) return false;
            forwardListHead = forwardListHead.next;
            reversedListHead = reversedListHead.next;
        }
        return true;
    }

    private ListNode? ReverseList(ListNode? head) {
        ListNode? iterator = head, previous = null;
        while (iterator != null) {
            var nextNode = iterator.next;
            iterator.next = previous;
            previous = iterator;
            iterator = nextNode;
        }
        return previous;
    }

    private ListNode? GetMiddle(ListNode? head) {
        ListNode? slow = head;
        ListNode? fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

Dart

class Solution {
  bool isPalindrome(ListNode? head) {
    ListNode? middleNode = getMiddle(head);
    ListNode? reversedListHead = reverseList(middleNode);
    ListNode? forwardListHead = head;

    while (forwardListHead != null && reversedListHead != null) {
      if (forwardListHead.data != reversedListHead.data) return false;
      forwardListHead = forwardListHead.next;
      reversedListHead = reversedListHead.next;
    }
    return true;
  }

  ListNode? reverseList(ListNode? head) {
    ListNode? iterator = head;
    ListNode? previous = null;
    while (iterator != null) {
      ListNode? nextNode = iterator.next;
      iterator.next = previous;
      previous = iterator;
      iterator = nextNode;
    }
    return previous;
  }

  ListNode? getMiddle(ListNode? head) {
    ListNode? slow = head;
    ListNode? fast = head;
    while (fast != null && fast.next != null) {
      slow = slow?.next;
      fast = fast.next?.next;
    }
    return slow;
  }
}

PHP

class Solution {
    public function isPalindrome(?ListNode $head): bool {
        $middleNode = $this->getMiddle($head);
        $reversedListHead = $this->reverseList($middleNode);
        $forwardListHead = $head;

        while ($forwardListHead !== null && $reversedListHead !== null) {
            if ($forwardListHead->data !== $reversedListHead->data) return false;
            $forwardListHead = $forwardListHead->next;
            $reversedListHead = $reversedListHead->next;
        }
        return true;
    }

    private function reverseList(?ListNode $head): ?ListNode {
        $iterator = $head;
        $previous = null;
        while ($iterator !== null) {
            $nextNode = $iterator->next;
            $iterator->next = $previous;
            $previous = $iterator;
            $iterator = $nextNode;
        }
        return $previous;
    }

    private function getMiddle(?ListNode $head): ?ListNode {
        $slow = $head;
        $fast = $head;
        while ($fast !== null && $fast->next !== null) {
            $slow = $slow->next;
            $fast = $fast->next->next;
        }
        return $slow;
    }
}

Ruby

class Solution
  def palindrome?(head)
    middle_node = get_middle(head)
    reversed_list_head = reverse_list(middle_node)
    forward_list_head = head

    while forward_list_head && reversed_list_head
      return false if forward_list_head.data != reversed_list_head.data
      forward_list_head = forward_list_head.next
      reversed_list_head = reversed_list_head.next
    end
    true
  end

  def reverse_list(head)
    iterator, previous = head, nil
    while iterator
      next_node = iterator.next
      iterator.next = previous
      previous = iterator
      iterator = next_node
    end
    previous
  end

  def get_middle(head)
    slow, fast = head, head
    while fast && fast.next
      slow = slow.next
      fast = fast.next.next
    end
    slow
  end
end