Problem 8.7 · Linked ListsEasy

Palindrome Linked List

PatternIn-Place Linked List Reversal Fast and Slow Pointers

What it teaches: Combine two techniques: find the middle with fast and slow, reverse the second half, then compare.

Practise it on judges as “Palindrome Linked List”.

The problem

Return true if the singly linked list reads the same forwards and backwards. Can you do it in O(n) time and O(1) space?

Example 1

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

Example 2

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

Constraints

1 ≤ nodes ≤ 10⁵
0 ≤ value ≤ 9

Pattern clues in the wording

→ Palindrome check, but you can't walk backwards
→ O(1) space follow-up

These clues point to In-Place Linked List Reversal: Walk the list with prev, curr and next, turning each arrow around as you go.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public boolean isPalindrome(ListNode head) {
        return true;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	head = [1,2,2,1]	true
2	head = [1,2]	false

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Copy to a list · O(n)2. Optimal: reverse the second half · O(n)

Copy to a list

Time O(n) Space O(n)

Copy values into an ArrayList and check it with two pointers.

Approach 1

import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> vals = new ArrayList<>();
        for (ListNode p = head; p != null; p = p.next) vals.add(p.val);
        for (int i = 0, j = vals.size() - 1; i < j; i++, j--)
            if (!vals.get(i).equals(vals.get(j))) return false;
        return true;
    }
}

Verdict: Easy, but uses O(n) memory.

Optimal: reverse the second half

Time O(n) Space O(1)

Fast and slow find the middle. Reverse from slow to the end. Walk from the head and from the reversed half's head together, comparing values.

Approach 2

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode prev = null;                 // reverse from slow to the end
        while (slow != null) {
            ListNode next = slow.next;
            slow.next = prev;
            prev = slow;
            slow = next;
        }
        for (ListNode a = head, b = prev; b != null; a = a.next, b = b.next)
            if (a.val != b.val) return false;
        return true;
    }
}

Verdict: Constant memory. (Mention that it modifies the list; reverse the half back if the caller needs the original.)

Before you submit

Edge cases and common mistakes

Test these inputs

One node
Two nodes
Odd length (the middle compares with itself)

Mistakes people make

Comparing Integer objects with != in the list version.
Walking the first half until null (it still links into the reversed part); compare until the reversed half ends.

Interview

Follow-up questions

How do you restore the list afterwards?

Command Palette