题目链接

234. 回文链表

题目描述

请判断一个链表是否为回文链表。

示例：

输入：head = [1,2,2,1]
输出：true

解题思路

1. 栈

利用栈 “先进后出” 的特点，可以将链表逆序，然后遍历比较即可。

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

• 时间复杂度：
• 空间复杂度：，开辟栈需要的额外空间，N 取决于链表长度。

  2. 找中点 + 反转链表

根据 “回文” 的特点，可以将链表从中间分为前后两部分，将后半部分链表反转后，分别遍历比较前后两部分链表节点值，如果节点值不相等则说明不是回文链表。

class Solution {
    public boolean isPalindrome(ListNode head) {
        // 1. 快慢指针找中点
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // succ 后半部分
        ListNode succ = slow.next;
        slow.next = null;
        // 2. 反转后半部分链表
        succ = reverse(succ);
        // 当链表长度为奇数时，前半部分链表会比后半部分链表多一个节点，所以只需要判断后半部分是否到 null
        while (succ != null) {
            if (head.val != succ.val) {
                return false;
            }
            head = head.next;
            succ = succ.next;
        }
        return true;
    }
    public ListNode reverse(ListNode head) {
        ListNode pre = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = pre;
            pre = head;
            head = temp;
        }
        return pre;
    }
}

• 时间复杂度：
• 空间复杂度：