剑指 Offer II 027. 回文链表

Posted on | In
Words count in article: 195 | Reading time ≈ 1

题目

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

示例1：

1
2
输入: head = [1,2,3,3,2,1]
输出: true

示例2：

1
2
输入: head = [1,2]
输出: false

提示：

  • 链表 L 的长度范围为 [1, 10^5]
  • 0 <= node.val <= 9

进阶：

能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

解法一：

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean isPalindrome(ListNode head) {
        if (Objects.isNull(head)) {
            return false;
        }
        List<Integer> result = new ArrayList<>();
        while (!Objects.isNull(head)) {
            result.add(head.val);
            head = head.next;
        }

        int begin = 0;
        int end = result.size() - 1;
        while (begin < end) {
            if (result.get(begin++) != result.get(end--)) {
                return false;
            }
        }
        return true;
    }
0%