大家好，我是前端西瓜哥，今天来做一道算法题。
给一个单链表，判断是否为回文链表。
所谓回文，就是左右值对称相同的链表，比如 [1,2,1]、[1,2,2,1]。而像 [1,2,3] 这种则不是回文链表。
function isPalindrome(head: ListNode | null): boolean {
// 实现
};LeetCode 对应为 234 题，难度标记为简单，我不是很认可的。
大概因为大家都先转换为数组，然后头尾指针往中间靠近，一一对比，那确实简单很多。
但面试的时候，大概率是要求空间复杂度是 O(1) 的，即不许用数组。如果可以用数组，直接给一个数组问是否为回文数组就行了。
如果不能用数组，那这题就是中等难度，它是几道题目的组合：
- 查找链表的中间节点。对应 876 题，但稍有区别，对于有两个中间节点的情况，要返回左边那一个。
- 反转数组。对应 206 题。
然后再做双指针遍历对比。
我们先搭一个框架：
function isPalindrome(head: ListNode | null): boolean {
if (!head || head.next == null) return true;
// 找到中间节点位置
const midNode = findMidNode(head);
// 反转右侧一半
const head2 = reverse(midNode.next);
// 遍历两个链表，进行对比。
let p = head;
let q = head2;
while (q != null) {
if (p.val !== q.val) return false;
p = p.next;
q = q.next;
}
return true;
};查找中间节点的实现：
function findMidNode (head: ListNode): ListNode {
let slow = head;
let fast = head;
// 对于偶数，要取左侧的那个
while (fast != null && fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}对于有两个中间节点的情况，这里的实现是取左边那一个。如果你要取右边那一个，就要改为 while (fast != null && fast.next != null)。
循环结束条件，可以通过举例来验证是否正确。
然后是反转链表的实现：
function reverse(head: ListNode): ListNode {
let pre = null;
let p = head;
while (p != null) {
const next = p.next;
p.next = pre;
pre = p;
p = next;
}
return pre;
}因为我们反转的是比较短的右侧链表（链头为 midNode.next），所以我们对比两个链表的结束条件为右侧侧链表指针指向 null。
let p = head;
let q = head2;
while (q != null) {
if (p.val !== q.val) return false;
p = p.next;
q = q.next;
}
return true;结尾
链表题，本质上来说是编程题，不是技巧题，它朴实无华，考察你的细心程度。
我是前端西瓜哥，关注我，一起学习前端知识。
网友评论