Palindrome Linked List

Decide whether a singly linked list reads the same forward and backward. The classic exercise in finding the middle with fast and slow pointers and reversing half a list. Solve it below in Python or JavaScript, then read the walkthrough.

Solve it in your browser Read the solution

EasyLinked List Two Pointers Stack Recursion Asked at 95 companies incl. Google, Amazon, Meta

Problem

You're given the head of a singly linked list. Return true if the sequence of values reads the same from head to tail as it does from tail to head, and false otherwise.

In the tests, the list is written as an array from head to tail. Try to solve it in O(n) time with O(1) extra space.

Example 1

Input: head = [3, 7, 7, 3]
Output: true

Example 2

Input: head = [4, 8, 4]
Output: true

With an odd length, the middle value only has to match itself.

Example 3

Input: head = [1, 0, 0]
Output: false

Backward it reads 0, 0, 1.

Constraints

The list has between 1 and 10⁵ nodes.
0 ≤ Node.val ≤ 9
Aim for O(n) time and O(1) extra space.

Practice

Runs 13 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.

Get asked Palindrome Linked List in a real interview?

Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.

Start Free Trial

How to solve Palindrome Linked List

Pattern: Fast/slow pointers plus in-place reversal

With an array you'd compare the two ends and move inward. A singly linked list can't walk backward, so the trick is to make the second half walk backward: reverse it in place.

To find where the second half starts, move a slow pointer one step and a fast pointer two steps at a time. When fast runs out, slow is at the middle. Reverse the list from there, then walk one pointer from head and one from the reversed half's head, comparing values. If the length is odd, the middle node ends up compared with itself or skipped, which is fine since it always matches.

Approach 1: Copy values into an array

Walk the list once and push every value into an array, then check the array with two pointers from both ends. Simple and correct, but it needs memory proportional to the list.

Time O(n) · Space O(n)

Approach 2: Recursion with a front pointer

Recurse to the end of the list, and as the calls return (tail first), compare each node with a front pointer that advances from the head. Elegant, but the call stack is O(n) deep and overflows on long lists.

Time O(n) · Space O(n) call stack

Approach 3: Reverse the second half

Use slow and fast pointers to find the middle.
Reverse the list starting at slow.
Compare values from head and from the reversed half until the reversed half ends. Any mismatch means false.
Optionally reverse the second half again to restore the input.

Time O(n) · Space O(1)

Approach	Time	Space
Copy values into an array	O(n)	O(n)
Recursion with a front pointer	O(n)	O(n) call stack
Reverse the second half	O(n)	O(1)

Solution code

Try the practice editor first. Both solutions pass every test above.

Palindrome Linked List solution in Python

def is_palindrome(head: Optional[ListNode]) -> bool:
    # Find the middle: slow ends at the start of the second half.
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Reverse the second half.
    prev = None
    while slow:
        nxt = slow.next
        slow.next = prev
        prev = slow
        slow = nxt

    # 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

Palindrome Linked List solution in JavaScript

function isPalindrome(head) {
  // Find the middle: slow ends at the start of the second half.
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  // Reverse the second half.
  let prev = null;
  while (slow) {
    const next = slow.next;
    slow.next = prev;
    prev = slow;
    slow = next;
  }

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

Common mistakes

Comparing node objects instead of their values.
Getting the middle wrong on even lengths and comparing one half that is longer than the other by two.
Losing the rest of the list during reversal by overwriting next before saving it.
Using recursion on a 10⁵ node list, which hits the recursion limit in Python.

What interviewers look for

Mention the O(n) space array version first and say it's what you'd ship if memory isn't a concern. Then explain that the follow-up of O(1) space is what the interviewer is really asking about, and lay out the three steps before coding: find the middle, reverse, compare.

Interviewers often ask whether modifying the input is acceptable. Offer to reverse the second half back afterward so the caller sees the list unchanged.

Follow-up questions

How do you leave the list unchanged afterward?

Keep a pointer to the head of the reversed half, and after comparing, reverse it again and attach it back to the node before the middle. That restores the original order at the cost of one more O(n) pass.

What if it were a doubly linked list?

Walk to the tail, then move one pointer forward from the head and one backward from the tail until they meet, comparing values. O(n) time and O(1) space with no reversal.

What if the list is shared by other threads while you check it?

Reversing in place would corrupt what other readers see. Either take a lock for the duration, or use the array copy approach, which only reads the list.

Companies that ask Palindrome Linked List

Palindrome Linked List is tagged by 95 companies in our interview dataset. The score shows how often it comes up at each company.

and 71 more.

Get live help in the real interview

Working solutions in real time during your actual interview. Invisible to screensharing.

Start Free Trial

No credit card required

Palindrome Linked List

Solve it in your browser Read the solution

EasyLinked List Two Pointers Stack Recursion Asked at 95 companies incl. Google, Amazon, Meta

Problem

You're given the head of a singly linked list. Return true if the sequence of values reads the same from head to tail as it does from tail to head, and false otherwise.

In the tests, the list is written as an array from head to tail. Try to solve it in O(n) time with O(1) extra space.

Example 1

Input: head = [3, 7, 7, 3]
Output: true

Example 2

Input: head = [4, 8, 4]
Output: true

With an odd length, the middle value only has to match itself.

Example 3

Input: head = [1, 0, 0]
Output: false

Backward it reads 0, 0, 1.

Constraints

The list has between 1 and 10⁵ nodes.
0 ≤ Node.val ≤ 9
Aim for O(n) time and O(1) extra space.

Practice

Runs 13 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.

Get asked Palindrome Linked List in a real interview?

Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.

Start Free Trial

How to solve Palindrome Linked List

Pattern: Fast/slow pointers plus in-place reversal

With an array you'd compare the two ends and move inward. A singly linked list can't walk backward, so the trick is to make the second half walk backward: reverse it in place.

Approach 1: Copy values into an array

Walk the list once and push every value into an array, then check the array with two pointers from both ends. Simple and correct, but it needs memory proportional to the list.

Time O(n) · Space O(n)

Approach 2: Recursion with a front pointer

Time O(n) · Space O(n) call stack

Approach 3: Reverse the second half

Use slow and fast pointers to find the middle.
Reverse the list starting at slow.
Compare values from head and from the reversed half until the reversed half ends. Any mismatch means false.
Optionally reverse the second half again to restore the input.

Time O(n) · Space O(1)

Approach	Time	Space
Copy values into an array	O(n)	O(n)
Recursion with a front pointer	O(n)	O(n) call stack
Reverse the second half	O(n)	O(1)

Solution code

Try the practice editor first. Both solutions pass every test above.

Palindrome Linked List solution in Python

def is_palindrome(head: Optional[ListNode]) -> bool:
    # Find the middle: slow ends at the start of the second half.
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Reverse the second half.
    prev = None
    while slow:
        nxt = slow.next
        slow.next = prev
        prev = slow
        slow = nxt

    # 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

Palindrome Linked List solution in JavaScript

function isPalindrome(head) {
  // Find the middle: slow ends at the start of the second half.
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  // Reverse the second half.
  let prev = null;
  while (slow) {
    const next = slow.next;
    slow.next = prev;
    prev = slow;
    slow = next;
  }

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

Common mistakes

Comparing node objects instead of their values.
Getting the middle wrong on even lengths and comparing one half that is longer than the other by two.
Losing the rest of the list during reversal by overwriting next before saving it.
Using recursion on a 10⁵ node list, which hits the recursion limit in Python.

What interviewers look for

Interviewers often ask whether modifying the input is acceptable. Offer to reverse the second half back afterward so the caller sees the list unchanged.

Follow-up questions

How do you leave the list unchanged afterward?

What if it were a doubly linked list?

Walk to the tail, then move one pointer forward from the head and one backward from the tail until they meet, comparing values. O(n) time and O(1) space with no reversal.

What if the list is shared by other threads while you check it?

Reversing in place would corrupt what other readers see. Either take a lock for the duration, or use the array copy approach, which only reads the list.

Companies that ask Palindrome Linked List

Palindrome Linked List is tagged by 95 companies in our interview dataset. The score shows how often it comes up at each company.

and 71 more.

Get live help in the real interview

Working solutions in real time during your actual interview. Invisible to screensharing.

Start Free Trial

No credit card required

Problem

Constraints

Practice

How to solve Palindrome Linked List

Approach 1: Copy values into an array

Approach 2: Recursion with a front pointer

Approach 3: Reverse the second half

Solution code

Common mistakes

What interviewers look for

Follow-up questions

How do you leave the list unchanged afterward?

What if it were a doubly linked list?

What if the list is shared by other threads while you check it?

Companies that ask Palindrome Linked List

Practice next

Get live help in the real interview

Problem

Constraints

Practice

How to solve Palindrome Linked List

Approach 1: Copy values into an array

Approach 2: Recursion with a front pointer

Approach 3: Reverse the second half

Solution code

Common mistakes

What interviewers look for

Follow-up questions

How do you leave the list unchanged afterward?

What if it were a doubly linked list?

What if the list is shared by other threads while you check it?

Companies that ask Palindrome Linked List

Practice next

Get live help in the real interview