Palindrome Linked List


Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Example 1:

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

Example 2:

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


  • The number of nodes in the list is in the range [1, 105].
  • 0 <= Node.val <= 9

Follow up: Could you do it in O(n) time and O(1) space?


I put this off for literally a month. Ah, oh well.

This is difficult to do with a linked list because we’d need forward and backward access to do a palindrome check. This means we either have to copy the linked list to another data structure, or have a very computationally inefficient solution. I suspect the follow-up question is a trick. I don’t think it’s possible to do this in O(n) tiem and O(1) space unless we modified the data structure in-place somehow and made the singly linked list into a doubly linked list.

Using a data structure is likely better.

Alternatively, we could reverse the second half of the linked list. Reversing would be… O(n) time and O(1) space.


We want to find the second half of the linked list and reverse it.

For example, if we’re given 1, 2, 3, 2, 1:

  • Ignore the 3 in the middle. If there is an exact middle in a pallindrome then it is irrelevant
  • Split the list into a left and right section. The left section will contain 1, 2. The right section will contain 2, 1.
  • Reverse the right section from 2, 1 to 1, 2.
  • Check.

I didn’t actually implement this solution.


 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; = next; }
 * }
class Solution {
    public boolean isPalindrome(ListNode head) {
        // convert the linked list to an array list
        var a = new ArrayList<Integer>();
        while (head != null) {
            head =;

        // now we can use any 'ol algorithm to check
        var l = 0;
        var r = a.size() - 1;
        while (l < r) {
            if (!a.get(l).equals(a.get(r))) {
                return false;
            l += 1;
            r -= 1;

        return true;

Recent posts from blogs that I like

Guerrilla event planning at larger conferences

How to capitalism with care

via Xe Iaso

Creating an already-completed asynchronous activity in C++/WinRT, part 9

Cheating the delegates. The post Creating an already-completed asynchronous activity in C++/WinRT, part 9 appeared first on The Old New Thing.

via The Old New Thing

Weeknotes: GPT-4o mini, LLM 0.15, sqlite-utils 3.37 and building a staging environment

via Simon Willison