前年面摩根士丹利的時(shí)候被Joshua大哥問過的題铐拐。當(dāng)時(shí)墨跡半天我也只是說出來要把鏈表反轉(zhuǎn)一下再比較。(結(jié)果還是被要了练对。只能說人家讓過了遍蟋。其實(shí)當(dāng)時(shí)站在我的角度看，我已經(jīng)掛了螟凭。)

這次寫一個(gè)完整的做法：
先找到鏈表的中點(diǎn)虚青，用一快一慢兩個(gè)指針，快的一次走兩步螺男，慢的一次走一步棒厘∽荽快的到頭的時(shí)候，慢的正好在中間奢人。
然后從鏈表的中點(diǎn)開始谓媒，將后半段反轉(zhuǎn)。
然后用兩個(gè)指針何乎。一個(gè)指向原鏈表的起點(diǎn)句惯。另一個(gè)指向被反轉(zhuǎn)部分的起點(diǎn)。
兩個(gè)指針挨個(gè)遍歷支救。如果遇到不一樣的宗弯，就說明不是回文。

比如這樣：
原鏈表： 1 -> 2 -> 3 -> 4 -> 1
從中間反轉(zhuǎn)之后 1-> 4->3
從原鏈表和反轉(zhuǎn)之后的鏈表分別遍歷
1 == 1 繼續(xù)
4 != 2 說明不是回文搂妻。

提供的方法：
private class ListNode 自己定義的做鏈表的節(jié)點(diǎn)
private boolean isStringPalindrome(String input) 用來測(cè)試回文的方法
private ListNode reverseLinkedList(ListNode head)反轉(zhuǎn)一個(gè)鏈表
private ListNode getLinkedListFromString(String input)測(cè)試用。將輸入的字符串變成鏈表
private void printList(ListNode head)調(diào)試用辕棚。打印鏈表欲主。

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

}