Palindrome Linked List

Easy Linked List Front Middle Back Pointer Original on LeetCode

Palindrome Linked List is a easy linked list problem solved with the front middle back pointer pattern. The best approach, optimal (middle + reverse second half), runs in O(n) time and O(1) space. Below are 2 approaches in Java, from copy to an array up.

Problem

Decide whether the values of a singly linked list read the same forwards and backwards.

Examples

Example 1

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

Example 2

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

Constraints

The list has 1 to 10^5 nodes.
Follow-up: O(n) time and O(1) space.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Copy to an array	`O(n)`	`O(n)`
Optimal (middle + reverse second half)	`O(n)`	`O(1)`

1Copy to an array

TimeO(n)

SpaceO(n)

Copy values into a list and check it with two pointers.

Copy values; compare i from the front and j from the back.

Java

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

2Optimal (middle + reverse second half)

TimeO(n)

SpaceO(1)

Use slow and fast pointers to reach the middle, reverse the second half in place, and compare it node by node with the first half. You can reverse it back afterwards to leave the list unchanged.

slow/fast to the middle (slow ends at the start of the second half).
Reverse from slow.
Compare head and the reversed half until the reversed half ends.

Java

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;
        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;
    }
}

Edge cases to test

Single node
Even vs odd length

Hints

Hint 1

Find the middle, reverse the second half, then compare the two halves.

FAQ

What is the best time complexity for Palindrome Linked List?

Optimal (middle + reverse second half) runs in O(n) time and O(1) extra space.

Which pattern does Palindrome Linked List use?

It is a linked list problem that uses the front middle back pointer pattern. Other problems with the same pattern: Reverse Linked List, Reverse Linked List II, Reverse Nodes in k-Group.

Is there a brute force solution for Palindrome Linked List?

Yes. Copy to an array takes O(n) time and O(n) space. Copy values into a list and check it with two pointers.

Which edge cases should I test for Palindrome Linked List?

Single node; Even vs odd length.