5. 用链表检测回文

前年面摩根士丹利的时候被Joshua大哥问过的题。当时墨迹半天我也只是说出来要把链表反转一下再比较。(结果还是被要了。只能说人家让过了。其实当时站在我的角度看，我已经挂了。)

这次写一个完整的做法：
先找到链表的中点，用一快一慢两个指针，快的一次走两步，慢的一次走一步。快的到头的时候，慢的正好在中间。
然后从链表的中点开始，将后半段反转。
然后用两个指针。一个指向原链表的起点。另一个指向被反转部分的起点。
两个指针挨个遍历。如果遇到不一样的，就说明不是回文。

比如这样：
原链表： 1 -> 2 -> 3 -> 4 -> 1
从中间反转之后 1-> 4->3
从原链表和反转之后的链表分别遍历
1 == 1 继续
4 != 2 说明不是回文。

提供的方法：
private class ListNode 自己定义的做链表的节点
private boolean isStringPalindrome(String input) 用来测试回文的方法
private ListNode reverseLinkedList(ListNode head)反转一个链表
private ListNode getLinkedListFromString(String input)测试用。将输入的字符串变成链表
private void printList(ListNode head)调试用。打印链表。

public class TestPalindrome {

    private class ListNode {
        char val;
        ListNode next;
        ListNode(){}
        ListNode(char val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        TestPalindrome tp = new TestPalindrome();

        System.out.println(tp.isStringPalindrome("abcba")); // true
        System.out.println(tp.isStringPalindrome("abccba")); // true
        System.out.println(tp.isStringPalindrome("12345")); // false
        System.out.println(tp.isStringPalindrome("12346")); // false
        System.out.println(tp.isStringPalindrome("1")); // true
        System.out.println(tp.isStringPalindrome("")); // true
        System.out.println(tp.isStringPalindrome(null)); // false
    }

    private boolean isStringPalindrome(String input) {
        if (input == null) {return false;}
        if (input.isEmpty()) {return true;}
        ListNode head = getLinkedListFromString(input);
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode reversedSecondHalf = reverseLinkedList(slow);
        ListNode beginPointer = head;
        ListNode endPointer = reversedSecondHalf;
        while(endPointer != null) {
            if (beginPointer.val == endPointer.val) {
                endPointer = endPointer.next;
                beginPointer = beginPointer.next;
                continue;
            }
            return false;
        }
        return true;

    }

    private ListNode reverseLinkedList(ListNode head) {
        ListNode prevNode;
        ListNode currNode;
        ListNode dummy = new ListNode();
        dummy.next = head;
        prevNode = dummy;
        currNode = head;
        while(currNode != null) {
            ListNode temp = currNode.next;
            currNode.next = prevNode;
            prevNode = currNode;
            currNode = temp;
        }
        dummy.next.next = null; // remove the
        return prevNode;
    }

    private ListNode getLinkedListFromString(String input) {
        ListNode dummy = new ListNode();
        ListNode prev = dummy;
        char[] chars = input.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            ListNode node = new ListNode(chars[i]);
            node.val = chars[i];
            prev.next = node;
            prev = prev.next;
        }
        return dummy.next;
    }

    private void printList(ListNode head) {
        ListNode pointer = head;
        while (pointer != null) {
            System.out.print(pointer.val + " ; ");
            pointer = pointer.next;
        }
    }

}