image
题目描述
- 等级:
简单
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 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]
注意：
- 偶数个的数字也有回文数124421
- 小数没有回文数
链表反转请参考：反转单链表
通过两个快慢指针可以获取链表中的中间位置节点。（快慢指针步数相差一倍）
答案
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
