leetcode--PalindromeLinkedList

思路：

為了達到O(N)的時間複雜度和O(1)的空間複雜度，分成三步完成。

1.利用快慢指針找到中間節點

2.從中間節點到尾部反轉連結清單

3.從頭和尾向中間周遊，判斷是否相等

public boolean isPalindrome(ListNode head) {
        if(head==null)return true;
        ListNode mid = findMiddle(head);
        ListNode last = reverse(mid);
        boolean isPalindrome = true;
        while (head != null) {
            if (head.val != last.val) isPalindrome = false;
            head=head.next;
            last=last.next;
        }
        return isPalindrome;
    }

    public ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null) {
            if (fast.next.next == null) break;
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public ListNode reverse(ListNode head) {
        ListNode pre = head;
        ListNode current = head.next;
        while (current != null) {
            ListNode next = current.next;
            current.next = pre;
            pre = current;
            current = next;
        }
        head.next = null;
        return pre;
    }