【LeetCode】234. Palindrome Linked List

    //Method 1: reverse half of the list
    public boolean isPalindrome(ListNode head) {
        if(head==null)
            return true;
        ListNode slow = head, fast = head;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        if(fast!=null) // odd nodes: let right half smaller
            slow = slow.next;
        slow = reverse(slow);
        while(slow!=null){
            if(head.val != slow.val)
                return false;
            head=head.next;
            slow=slow.next;
        }
        return true;
    }
    
    public ListNode reverse(ListNode node){
        ListNode pre = null;
        ListNode cur = node;
        while(cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    
    
    //Method 2: use a stack to store
    public boolean isPalindrome1(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode node = head;
        while(node!=null){
            stack.push(node);
            node=node.next;
        }
        while(!stack.isEmpty()){
            if(head.val != stack.pop().val)
                return false;
            head=head.next;
        }
        return true;
    }