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;
    }
}