一、题目内容

二、题解

解法1：

思路

反转后半部分
fast！=null时，说明是奇数长度

代码

public class Solution {
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        // write code here
        ListNode fast = head, slow = head;
        //通过快慢指针找到中点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        if(fast!=null){
            slow = slow.next;
        }
        slow = reverse(slow);
        fast = head;
        while(slow !=null){
            if(fast.val!=slow.val){
                return false;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }
    private ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

解法2：

思路

队列

代码

public class Solution {
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        // write code here
        Deque<Integer> deque = new LinkedList<Integer>();
        while(head!=null){
            deque.offer(head.val);
            head = head.next;
        }
        while(deque.size()>=2){
            if(!deque.removeFirst().equals(deque.removeLast())){
                return false;
            }
        }
        return deque.isEmpty() || deque.size() == 1;
    }
}