Palindrome Linked List

Easy Problem 52 of 151 Java and Python

Problem

Given the head of a singly linked list, return true if it is a palindrome (reads the same forwards and backwards), otherwise false.

Example 1

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

Example 2

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

Constraints

1 ≤ number of nodes ≤ 10⁵
0 ≤ Node.val ≤ 9
Follow-up: O(n) time and O(1) space.

Explanation

You cannot walk a singly linked list backwards, so either copy it into an array or make the second half walk backwards by reversing it.

Find the middle with slow/fast pointers, reverse from there, and compare the first half with the reversed second half node by node.

Approach 1 · Naive

Copy into an array

Time O(n)
Space O(n)

Copy the values to an array and check it with two pointers.

Collect values.
Compare values[i] with values[n - 1 - i].

Java

import java.util.*;

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

Python

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        values = []
        while head:
            values.append(head.val)
            head = head.next
        return values == values[::-1]

Approach 2 · Optimal

Reverse the second half

Time O(n)
Space O(1)

Find the middle, reverse the second half in place, and walk both halves together.

Use slow/fast pointers to stop slow at the middle.
Reverse the list starting at slow.
Compare values from head and from the reversed half until the reversed half ends.

Java

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head;
        ListNode 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;
    }
}

Python

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        prev = None
        while slow:
            slow.next, prev, slow = prev, slow, slow.next
        a, b = head, prev
        while b:
            if a.val != b.val:
                return False
            a, b = a.next, b.next
        return True

Complexity compared

Approach	Time	Space
Naive Copy into an array	O(n)	O(n)
Optimal Reverse the second half	O(n)	O(1)

Key takeaways

This modifies the input list. In an interview, mention that you would reverse the second half back afterwards if the caller still needs it.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem