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, Python, C++ and JavaScript, 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.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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.

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 code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Copy to an arrayO(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.

  1. Copy values; compare i from the front and j from the back.
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.

  1. slow/fast to the middle (slow ends at the start of the second half).
  2. Reverse from slow.
  3. Compare head and the reversed half until the reversed half ends.
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.