trjhtr

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++) 
 firstHalf.add(node.val);
 node = node.next;
 

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

 for(int i = middle + 1; node != null; i++) 
 secondHalf.add(node.val);
 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; 

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).

Things I like about your approach:

• 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):

• missing doc comments
  
  
  • 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) 
 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");
 checkNodeList("Maddam");
 checkNodeList("maddam");
 checkNodeList("madDam");

[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");
 check("Maddam");
 check("maddam");
 check("madDam");


/** 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>() 
 ListNode head = ListNode.this;
 @Override
 public boolean hasNext() return null != head; 
 @Override
 public Integer next() 
 int v = head.val;
 head = head.next;
 return v;
 
 ;