Palindrome Linked List

Problem

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

Constraints:

  • 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?

Solution

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.

Splitting/Reversing

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.

Array

/**
 * 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; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        // convert the linked list to an array list
        var a = new ArrayList<Integer>();
        while (head != null) {
            a.add(head.val);
            head = head.next;
        }

        // 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

Paintings of the Franco-Prussian War: 2 The Siege of Paris

As winter grew colder, Parisians started to starve. A city known for its food and restaurants had to scavenge meals based on horse, dog, cat and even rat.

via The Eclectic Light Company

Impromptu disaster recovery

via fasterthanlime

Notes on implementing Attention

Some notes on implementing attention blocks in pure Python + Numpy. The focus here is on the exact implementation in code, explaining all the shapes throughout the process. The motivation for why attention works is not covered here - there are plenty of excellent online resources explaining it. Seve...

via Eli Bendersky