解法1:使用栈

出栈后和原来的节点对比，注意比较的是val，而不是节点本身：if(reverse.val != original.val)

时间复杂度：O(n)

空间复杂度：O(n)

import java.util.*;
public class Solution {
    public boolean isPail (ListNode head) {
        if (head == null) {
            return false;
        }

        Stack<ListNode> reversedList = new Stack<ListNode>();
        ListNode current = head;
        while(current != null){
            reversedList.push(current);
            current = current.next;
        }
        
        ListNode reverse = reversedList.pop();
        ListNode original = head;
        while(!reversedList.empty() && original != null){
            if(reverse.val != original.val){
                return false;
            }
            reverse = reversedList.pop();
            original = original.next;
        }
        return true;
    }
}

解法2:反转后半部分，双指针辅助寻找中点

时间复杂度：O(n)

空间复杂度：O(1)

import java.util.*;
public class Solution {
    public boolean isPail (ListNode head) {
        if (head == null) {
            return false;
        }
        
        ListNode reversedFromMiddle = reverse(getMiddleOfList(head));
        ListNode original = head;
        while (reversedFromMiddle != null) {
            if (reversedFromMiddle.val != original.val) {
                return false;
            }
            reversedFromMiddle = reversedFromMiddle.next;
            original = original.next;
        }
        return true;
    }

    private ListNode getMiddleOfList(ListNode head) {
        ListNode left = head;
        ListNode right = head;
        while (right != null && right.next != null) {
            left = left.next;
            right = right.next.next;
        }
        
        if (right == null) {
            return left;
        } else {
            return left.next;
        }
    }

    private ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode headOfReversed = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return headOfReversed;

    }
}