Leetcode/F家A家 -- 234. Palindrome Linked List(stack || fast/slow ptr)

234. Palindrome Linked List(stack or fast/slow ptr)
easy
https://leetcode.com/problems/palindrome-linked-list/
Given a singly linked list, determine if it is a palindrome

思路1： reverse the half of the list and compare. Watch case for odd nodes
            eg(1,2,3,4 -- slow is newhead at 3, fast is null)
            eg(1,2,3,4,5 -- slow is at 3, fast at 5. the newhead is slow.next)
Complexity: O(n) time O(1) space

public class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head==null||head.next==null)return true;
        ListNode slow = head, fast = head;
        while(fast !=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        if(fast != null) slow = slow.next;//odd nodes
        ListNode newhead = reverseList(slow);
        while(newhead !=null){//use new list, if odd nodes, the center one is skiped
            if(head.val!=newhead.val)return false;
            head = head.next;
            newhead = newhead.next;
        }
        return true;
    }
    private ListNode reverseList(ListNode head){
        if(head==null||head.next==null){ return head;}
        ListNode prev = null;
        while(head!=null){
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;//prev is newhead, head is null
    }
}

思路2： use stack to store list nodes and compare with normal order.
Complexity: time O(n) space O(n)

public class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head==null||head.next==null)return true;
        Deque<ListNode> stack = new LinkedList<ListNode>();
        ListNode cur = head;
        while(cur!=null){
            stack.push(cur);
            cur = cur.next;
        }
        while(!stack.isEmpty()){
            if(head.val!=stack.pop().val){return false;}
            head = head.next;
        }
        return true;
    }
}