leetcode （Palindrome Linked List）

Title： Linked List Cycle     141

Difficulty：Easy

原題leetcode位址:   https://leetcode.com/problems/linked-list-cycle/

1.  雙指針、棧

時間複雜度：O(n)，兩次一層while循環，最長長度為n。

空間複雜度：O(1)，沒有申請額外空間。

/**
     * 雙指針，結合棧的應用
     * @param head
     * @return
     */
    public static boolean isPalindrome(ListNode head) {

        if (head == null || head.next == null) {
            return true;
        }

        Stack<ListNode> stack = new Stack<>();
        ListNode slower = head;
        ListNode faster = head;

        stack.push(head);
        while (faster.next != null && faster.next.next != null) {
            faster = faster.next.next;
            slower = slower.next;
            stack.push(slower);
        }

        if (faster.next != null) { // Listed為偶數
            slower = slower.next;
        }

        ListNode cur = slower;

        while (cur != null) {
            if (cur.val != stack.pop().val) {
                return false;
            }
            cur = cur.next;
        }

        return true;

    }