示例 1:

输入: 1->2

输出: false

示例 2:

输入: 1->2->2->1

输出: true

进阶：

你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) { val = x; }

 * }

 */

class Solution {

      public static boolean isPalindrome(ListNode head) {

        //借助一个栈和一个队列去判断

        Deque<ListNode> deque = new LinkedList<>();

        Stack<ListNode> helper = new Stack<>();

        int count = 0;

        while (head != null) {

            deque.addLast(head);

            helper.push(head);

            head = head.next;

            count++;

        }

        for (int i = 0; i < count; i++) {

            if (deque.poll().val != helper.pop().val) {

                return false;

            }

        }

        return true;

    }

}

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) { val = x; }

 * }

 */

class Solution {

       //快慢指针：边遍历边翻转前半段

    public static boolean isPalindrome(ListNode head) {

        if (head == null || head.next == null) {

            return true;

        }

        ListNode slow = head;

        ListNode fast = head.next;

        ListNode preNode = null;

        ListNode pre2Node = null;

        while (fast != null && fast.next != null) {

            preNode = slow;

            //此处因为不能丢失slow.next，所以使用preNode和pre2Node实现链表的翻转

            slow = slow.next;

            fast = fast.next.next;

            preNode.next = pre2Node;

            pre2Node = preNode;

        }

        //链表被分成两个部分,qNode表示后链表的头

        ListNode qNode = slow.next;

        //注意，因为之前没有指定slow.next指向哪个节点，此处要做指定（之前为了持续遍历，slow.next一直指向原链表的下一个节点）

        slow.next = preNode;

        //考虑奇偶：如果链表节点个数为偶数，则前链表的表头为slow,否则为slow.next

        ListNode pNode = fast == null ? slow.next : slow;

        while (qNode != null && pNode != null) {

            if (qNode.val != pNode.val) {

                return false;

            }

            qNode = qNode.next;

            pNode = pNode.next;

        }

        return true;

    }

}