Implement a function to check if a linked list is a palindrome.

Hint

• A palindrome is something which is the same when written forwards and backwards. What if you reversed the linked list?
• Try using a stack.
• Assume you have the length of the linked list. Can you implement this recursively?
• In the recursive approach (we have the length of the list), the middle is the base case: isPermutation(middle) is true. The node x to the immediate left of the middle: What can that node do to check if x -> middle -> y forms a palindrome? Now suppose that checks out. What about the previous node a? If x -> middle -> y is a palindrome, how can it check that a -> x -> middle -> y-> b is a palindrome?
• Go back to the previous hint. Remember: There are ways to return multiple values. You can do this with a new class.

Solution

本题让我们判断一个链表是否为回文链表，由于不能随机访问结点，因此一个直接的思路便是先把所有结点压入一个stack，然后再次遍历链表同时将结点出栈，比较两者的值是否对应相等即可。前面的方法需要遍历两次链表，我们可以进一步优化，利用快慢指针（慢指针1步，快指针2步）找到链表中点后，直接继续遍历后半段即可进行比较。

public static boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) return true; 
    Deque<Integer> stack = new LinkedList<>();
    stack.push(head.val);   
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        stack.push(slow.val);
    }
    if (fast.next == null) stack.pop(); // 结点数为奇数时，去掉中间结点   
    while (slow.next != null) {
        slow = slow.next;
        if (slow.val != stack.pop()) return false;
    }
    return true;
}