# Is the singly linked list a palindrome?

I have solved this question on Leetcode: https://leetcode.com/problems/palindrome-linked-list/description/. I convert the nodes into an ArrayList and am wondering if that's cheating? Other than that, how can I optimize this solution:

public class PalindromeLinkedList {

public static void main(String[] args) {
ListNode node = new ListNode(0);
node.next = new ListNode(0);
//node.next.next = new ListNode(1);
//node.next.next.next = new ListNode(1);

ArrayList firstHalf = new ArrayList();
ArrayList secondHalf = new ArrayList();

int count = 0;

ListNode counterNode = node;
while(counterNode != null) {
count++;
counterNode = counterNode.next;
}

int middle = count/2;
boolean middleIgnored = count%2 != 0;
for(int i = 0; i < middle; i++) {
node = node.next;
}

if(middleIgnored) {
node = node.next;
System.out.println("middle ignored");
}

for(int i = middle + 1; node != null; i++) {
node = node.next;
}

Collections.reverse(secondHalf);
boolean isPalindrome = firstHalf.equals(secondHalf);

System.out.println("first half: " + firstHalf);
System.out.println("\nsecond half: " + secondHalf);
System.out.println("\npalindrome? " + isPalindrome);

}

}

class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}

• (Welcome to CR!) The problem description on leetcode is short enough to quote here (which, given proper attribution, I consider fair use). The way I read that question: code isPalindrome() and, as a follow-up, answer: can a single solution achieve O(n) time and O(1) space? (My follow-up: Without at least temporarily modifying the input?) – greybeard Feb 5 '18 at 0:47

LeetCode seems to stress preparation for technical interviews, I consider it prudent to start sketching the most simple thing that could possibly do (I take the liberty to substitute the original last word work).

• conceptually simple & clean:
comparing first and last half with one reversed
• relying on runtime support in the environment of choice
for comparison and reversal

I do not consider transforming data to facilitate processing cheating, unless it explicitly violates part of the task description.
Things I don't like (this far, you saw it coming) about the execution (of said approach):

• e.g. about a known shortcoming:
using O(n) additional space out of convenience, not need
• not defining an explicit predicate isPalindrome()
• transforming more than one part of the linked list separately
• using repeated code (this may be appropriate in an interview setting, if commented (preferably in the code sketch, too))
• declaring the Lists for what they are (implementing class) instead of what use they are (interface)

Giving it a try:

/** Checks a home-grown linked list
* for <i>palindrome</i> using linear additional space.
* @param node the first node of the list to check, or <code>null</code>
* @return the order of values in the list
*  starting from <code>node</code> stays the same when reversed
*/// compare first half to reverse of second half
static boolean isPalindrome(final ListNode node) {
final List<Integer> items = new java.util.ArrayList<>();

for (ListNode n = node ; n != null; n = n.next)

int count = items.size(),
middle = count/2; // middle item in neither sublist for odd count
final List<Integer> tail = items.subList(count-middle, count);
java.util.Collections.reverse(tail);
return count < 2 ||
items.subList(0, middle).equals(tail);
}
/** Builds a node list from values & prints result of isPalindrome() */
static void checkNodeList(String values) {
ListNode node, n = node = new ListNode(42); // dummy
for (byte c: values.getBytes())
n = n.next = new ListNode(c);
node = node.next; // skip dummy
System.out.println("palindrome(" + values
+ "): " + isPalindrome(node));
}
public static void main(String[] args) {
checkNodeList("");
checkNodeList("?");
checkNodeList("!!");
checkNodeList("codedoc");
checkNodeList("codedoC");
checkNodeList("cOdedoc");
}


[optimizing] this solution - I can't make approach or code any clearer.
LeetCode's follow on: can a single solution achieve O(n) time and O(1) space?:
I know how to do it modifying the input, I doubt it can be done without.
There are many ways to skin cats, thinking how easy it would be using python, I gave turning ListNodes into Lists a try, with loop jamming and use of a sentinel thrown in:

/** Checks a home-grown linked <code>List</code>
* for <i>palindrome</i> using constant additional space.
* <br/>Temporarily modifies the list starting with <code>node</code>.
* @param node <code>null</code>, or the first node of the
*  <code>List</code> to check
* @return the order of values in the <code>List</code>
*  starting from <code>node</code> stays the same when reversed
*/
static boolean isPalindrome(final ListNode node) {
if (null == node)
return true;
ListNode
last,   // traverses list two steps/turn, stops at last node
middle, // middle of list part already traversed by last
reversed = null, // reverse of first half
slow = middle = last = node;
// jam "counting" and reversal of first half
for (ListNode next ; ; last = next.next) {
next = last.next;
middle = slow.next;
if (null == next)
break;
slow.next = reversed;
reversed = slow;
slow = middle;
if (null == next.next) {
last = next;
break;
}
}
if (null == reversed)
return true;
boolean mayBePalindrome = last.val == node.val;
if (mayBePalindrome) {
last.val = ~node.val; // turn last into sentinel
// jam "check" and restoration of first half; single comparison
while (reversed.val == middle.val) {
ListNode n = reversed.next;
reversed.next = slow;
slow = reversed;
reversed = n;
middle = middle.next;
}
mayBePalindrome &= middle == last;
last.val = node.val; // restore
}
while (null != reversed) {
ListNode n = reversed.next;
reversed.next = slow;
slow = reversed;
reversed = n;
}
return isPalindrome;
}

/** Prints result of isPalindrome() */
static void check(String init) {
ListNode node = null == init
? null : new ListNode(init, null);
System.out.println("palindrome(" + node
+ "): " + isPalindrome(node));
}

public static void main(String[] args) {
check(null);
check("'");
check("cc");
check("codedoc");
check("codedoC");
check("cOdedoc");
}

/** Singly-linked list node class bolstered some to support
* <code>java.util.List</code> iteration. */
static class ListNode extends java.util.AbstractList<Integer>
implements List<Integer>
{
int val;
ListNode next;
ListNode(int x) { val = x; }
ListNode(int x, ListNode n) { val = x; next = n; }
ListNode(String init, ListNode n) {
next = n;
if (null != init && 0 < init.length()) {
val = init.charAt(0);
if (1 < init.length())
next = new ListNode(init.substring(1), n);
}
}
@Override
public Integer get(int index) {
if (0 == index)
return val;
if (index < 0)
throw new IllegalArgumentException("index < 0");
if (null == next)
throw new IllegalArgumentException("size <= index");
return next.get(index-1);
}
@Override
public int size() { return null == next ? 1 : 1 + next.size(); }
@Override
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {