234. 回文链表

234. 回文链表

两次遍历栈容器存储解法：

时间复杂度：O(2n)
空间复杂度：O(n)

class Solution {
    public boolean isPalindrome(ListNode head) {
        // - 初始化一个临时节点
        ListNode temp = head;
        // - 初始化一个栈容器
        Stack<Integer> stack = new Stack<>();
        // - 将链表中的全部元素存储到栈中
        while (null != temp){
            stack.push(temp.val);
            temp = temp.next;
        }
        // - 将临时节点重新指向链表的头节点
        temp = head;
        // - 再次循环链表
        while (null != temp){
            // - 如果存在元素不相同 则直接返回值false
            if(temp.val != stack.pop()){
                return false;
            }
            temp = temp.next;
        }
        return true;
    }
}

双指针-反转链表解法：

时间复杂度：O(2n)
空间复杂度：O(n)

    class Solution {
        public boolean isPalindrome(ListNode head) {
            // - 双指针解法
            ListNode fast = head;
            ListNode slow = head;
            // - 循环链表 移动指针
            while (null != fast && null != fast.next) {
                fast = fast.next.next;
                slow = slow.next;
            }

            // - 此处比较难理解：当fast = null 时 代表链表元素时奇数个，需要将慢指针向后移动一个节点
            if (fast != null) {
                slow = slow.next;
            }

            // - 反转链表
            slow = reverseListNode(slow);
            // - 快指针指向链表头节点
            fast = head;

            // - 循环慢指针
            while (null != slow) {
                // - 如果存在不相同的元素则返回false
                if (slow.val != fast.val) {
                    return false;
                }

                fast = fast.next;
                slow = slow.next;
            }
            return true;
        }

        private ListNode reverseListNode(ListNode head){
            if(null == head){
                return head;
            }

            // - 最简单的反转链表 最好背下来
            ListNode newHead = null;
            while (null != head){
                ListNode temp = head.next;
                head.next = newHead;
                newHead = head;
                head = temp;
            }
            return newHead;
        }
    }