0
\$\begingroup\$

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; }
}
\$\endgroup\$
  • \$\begingroup\$ (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?) \$\endgroup\$ – greybeard Feb 5 '18 at 0:47
1
\$\begingroup\$

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) {
    final List<Integer> items = new java.util.ArrayList<>();

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

    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");
    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;
                }
            };
    }
}
\$\endgroup\$
  • \$\begingroup\$ Thanks for taking the time to give me this feedback, much appreciated \$\endgroup\$ – tom44 Feb 8 '18 at 5:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.