Check if a Doubly Linked List Is a Palindrome

Given a doubly linked list, return true if its values read the same forwards and backwards.

Example 1

Text

Input:  1 <-> 2 <-> 3 <-> 2 <-> 1
Output: true

graph LR
    A["1"] <--> B["2"] <--> C["3"] <--> D["2"] <--> E["1"]

Example 2

Text

Input:  1 <-> 2 <-> 3
Output: false

Which type to use

In a doubly linked list, every node holds two references: next to the node after it and prev to the node before it. A hand-written Java node is a class with those two mutable fields, and null marks both ends.

The standard library already provides a doubly linked list, java.util.LinkedList<E>. iterator() walks forward from the head, and descendingIterator() walks backward from the tail using the prev links. Both iterators cost O(1) per step. LinkedList also implements Deque, so addFirst, addLast, peekFirst, and peekLast are O(1).

Java

import java.util.LinkedList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.addLast(2);
        list.addLast(3);
        list.addFirst(1);
        System.out.println(list + " first=" + list.peekFirst() + " last=" + list.peekLast());
        List<Integer> backward = new LinkedList<>();
        list.descendingIterator().forEachRemaining(backward::add);
        System.out.println(backward);
    }
}

Output

[1, 2, 3] first=1 last=3
[3, 2, 1]

Brute force: copy into an ArrayList and compare with its reverse

Java

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

public class Main {
    static boolean isPalindrome(LinkedList<Integer> list) {
        List<Integer> values = new ArrayList<>(list);
        for (int i = 0, j = values.size() - 1; i < j; i++, j--) {
            if (!values.get(i).equals(values.get(j))) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        LinkedList<Integer> yes = new LinkedList<>(List.of(1, 2, 3, 2, 1));
        LinkedList<Integer> no = new LinkedList<>(List.of(1, 2, 3));
        System.out.println(isPalindrome(yes) + " " + isPalindrome(no));
    }
}

Output

true false

Time: O(n). Space: O(n) for the copy.

Optimal: two pointers moving inward

Compare the first and last values, then the second and second-to-last, and so on, moving one pointer forward from the head and one backward from the tail. The forward iterator is the front pointer and descendingIterator() is the back pointer. Only size() / 2 comparisons are needed: after that, the pointers have met or crossed. Values are compared with equals, because == on two Integer objects compares references.

Walkthrough with 1 <-> 2 <-> 3 <-> 2 <-> 1:

step	front `next()`	back `next()`	equal?
1	1	1	yes
2	2	2	yes
3	not needed (`size() / 2` = 2 steps)		return true

Java

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class Main {
    static boolean isPalindrome(LinkedList<Integer> list) {
        Iterator<Integer> front = list.iterator();
        Iterator<Integer> back = list.descendingIterator();
        for (int i = 0; i < list.size() / 2; i++) { // the middle element of an odd list needs no partner
            if (!front.next().equals(back.next())) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        LinkedList<Integer> odd = new LinkedList<>(List.of(1, 2, 3, 2, 1));
        LinkedList<Integer> even = new LinkedList<>(List.of(4, 7, 7, 4));
        LinkedList<Integer> no = new LinkedList<>(List.of(1, 2, 3));
        LinkedList<Integer> empty = new LinkedList<>();
        System.out.println(isPalindrome(odd) + " " + isPalindrome(even) + " " + isPalindrome(no) + " " + isPalindrome(empty));
    }
}

Output

true true false true

Time: O(n): each node is visited once. Space: O(1).

For an odd length, the middle element is never compared, because size() / 2 rounds down. It doesn't need to match anything.

Singly linked lists (LeetCode 234)

A singly linked list (LeetCode 234) has no prev references, so there's no way to walk backwards. The O(1)-space approach:

Count the nodes (or use fast and slow pointers) to find the middle.
Detach the second half and reverse it with the pointer-reversal loop.
Compare the first half with the reversed second half.

Java

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

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static List<Integer> toList(ListNode list) {
        List<Integer> values = new ArrayList<>();
        for (ListNode node = list; node != null; node = node.next) {
            values.add(node.val);
        }
        return values;
    }

    static ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

    static boolean isPalindrome(ListNode head) {
        int len = 0;
        for (ListNode n = head; n != null; n = n.next) len++;
        if (len < 2) return true;
        // Walk to the last node of the first half, then detach the second half.
        ListNode mid = head;
        for (int i = 0; i < (len + 1) / 2 - 1; i++) {
            mid = mid.next;
        }
        ListNode second = reverse(mid.next);
        mid.next = null;

        ListNode first = head;
        while (first != null && second != null) {
            if (first.val != second.val) return false;
            first = first.next;
            second = second.next;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isPalindrome(fromArray(1, 2, 2, 1)) + " " + isPalindrome(fromArray(1, 2, 3, 2, 1)));
        System.out.println(isPalindrome(fromArray(1, 2)));
    }
}

Output

true true
false

Time: O(n). Space: O(1). (This version changes the input list. Reverse the second half back and reattach it if the caller still needs the list.)