题目描述

  • 等级: 简单
    请判断一个链表是否为回文链表。

示例 1:

1
2
输入: 1->2
输出: false

示例 2:

1
2
输入: 1->2->2->1
输出: true

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

思路

对于单链表，回文，快慢指针，链表反转的考察。

“回文”是指正读反读都能读通的句子，它是古今中外都有的一种修辞方式和文字游戏，如“我为人人，人人为我”等。在数学中也有这样一类数字有这样的特征，成为回文数（palindrome number）。 [1]
设n是一任意自然数。若将n的各位数字反向排列所得自然数n1与n相等，则称n为一回文数。例如，若n=1234321，则称n为一回文数；但若n=1234567，则n不是回文数。 [1]

注意：

  1. 偶数个的数字也有回文数124421
  2. 小数没有回文数

链表反转请参考：反转单链表

通过两个快慢指针可以获取链表中的中间位置节点。（快慢指针步数相差一倍）

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public boolean isPalindrome(ListNode head) {
        //1、边界检查，空链表与只有一个节点的链表直接返回true
        if (head == null || head.next == null) {
            return true;
        }

        //2、通过快慢指针找到链表中间位置
        ListNode fast = head;
        ListNode slow = head;
        //当快节点走到终点，则慢节点的位置正好为链表中间
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //fast作为后半段的起始节点
        fast = slow;
        //slow作为前半段的起始节点
        slow = head;

        //3、反转后半段链表
        //定义pre存储前一个节点
        ListNode pre = null;
        while (fast != null) {
            //指定当前要调整的点。
            ListNode temp = fast;
            //fast指针后移，走向下一个要被调整的点。
            fast = fast.next;
            //将当前的点反转
            temp.next = pre;
            //pre指针重置到最前
            pre = temp;
        }

        //4、对比前后两段链表是否相同
        //因为奇数个节点时，后半段链表比前半段链表多1个，所以循环时以前半段链表为主
        while (slow != null && pre != null) {
            if (slow.val != pre.val) {
                return false;
            }
            slow = slow.next;
            pre = pre.next;
        }
        return true;
    }

结果

234.png

tencent.jpg