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;

    }