leetcode234 回文链表 两种做法（stack(空间非O(1)），空间O(1)）

link: leetcode234 回文链表

方法1， 快慢指针，把前半部分存入栈中和后半部分比较

public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) return true;
        Stack<Integer> stack = new Stack<>();
        ListNode slow = head;
        ListNode fast = head;
        while(true){
            stack.push(slow.val);
            slow = slow.next;
            if(fast.next == null){//odd
                stack.pop();
                break;
            }
            if(fast.next.next == null){ //even
                break;
            }
            fast = fast.next.next;
        }
        boolean flag = true;
        while (!stack.empty() && slow != null){
            int temp = stack.pop();
            if(slow.val == temp){
                slow = slow.next;
            }else {
                flag = false;
                break;
            }
        }
        if(!stack.empty() || slow != null)
            flag = false;
            
            
        return flag;
    }

方法2， 快慢指针，把前半部分反转与后半部分比较

public boolean isPalindrome2(ListNode head) { // O(1)
        if(head == null || head.next == null) return true;
        if(head.next.next == null){
            if(head.next.val == head.val){
                return true;
            }else{
                return false;
            }
        }
        ListNode slow = head;
        ListNode fast = head;
        int cnt= 0;
        while(true){
            slow = slow.next;
            cnt ++;
            if(fast.next == null){//odd
                cnt --;
                break;
            }
            if(fast.next.next == null){ //even
                break;
            }
            fast = fast.next.next;
        }
        // System.out.println("after while, slow.val =" +slow.val);
        ListNode fan = head;
        ListNode temp = head;
        ListNode newHead = head;
        int n = 0;
        // System.out.println("cnt= " + cnt);
        while (n < cnt - 1){
            temp = fan.next;
            fan.next = fan.next.next;
            temp.next = newHead;
            newHead = temp;
            // System.out.println("temp =" +temp.val);
            n++;

        }
        fan.next = null;

        boolean f = true;
        while(true){
            // System.out.println(slow.val + " | " + newHead.val);
            if(slow.val == newHead.val){
                slow = slow.next;
                newHead = newHead.next;
            }else {
                f = false;
                break;
            }
            if(slow == null && newHead != null){
                f = false;
                break;
            }else if(slow != null && newHead == null){
                f = false;
                break;
            }else if(slow == null && newHead == null){
                break;
            }
        }
        return f;
    }