Palindrome Linked List-LeetCode#234

234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.
Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

回文链表
给出一个单链表，判断它是否是回文。
思路：定义两个链表，为 temp 与 rate。temp 每次走一步，rate 每次走两步，当 rate 走完的时候，temp 刚好到中间位置。用 Stack 记录 temp 每次走的 val 值，然后 temp 继续走完，每次与 Stack 栈顶的值比较。

public boolean isPalindrome(ListNode head) {
    if (head == null) return true;
    ListNode temp = head;
    ListNode rate = head;
    Stack<Integer> stack = new Stack<>();
    stack.push(head.val);
    while (rate.next != null && rate.next.next != null) {
        temp = temp.next;
        rate = rate.next.next;
        stack.push(temp.val);
    }
    if (rate.next == null) stack.pop();
    while (temp.next != null){
        temp = temp.next;
        if (temp.val != stack.peek()){
            return false;
        }
        stack.pop();
    }
    return true;
}