链表检测回文串
来源：4-5 从链表中删除元素
慕粉3884565
2022-07-01
function solution(head) {
if (head == null || head.next == null) {
return true;
}
let prev;
let slow = head;
let fast = head;
let i = 0;
while (fast != null && fast.next != null) {
fast = fast.next.next;
let next = slow.next;
slow.next = prev;
prev = slow;
slow = next;
i++;
}
console.log(i);
if (fast != null) {
slow = slow.next;
}
console.log(slow);
console.log(prev);
while (slow != null) {
if (slow.data != prev.data) {
return false;
}
slow = slow.next;
prev = prev.next;
}
return true;
}这是采用链表检测回文串
第一个红框逻辑便是将slow遍历到整个链表2/1位置
但是第二个红框进行比较不是很懂，prev逻辑有点懵逼 老师能够详细讲讲吗
详细讲讲算法流程
写回答
1回答
-
第一个红框的代码不仅仅将 slow 遍历到了链表 1/2 的位置，还把链表前半部分翻转了。所以，在第二个红框的部分，slow 在从链表的中间，向前遍历；prev 在从链表的中间，向后遍历。每次 slow 和 prev 指向的内容相同，才说明是回文串，否则就不是。
这里面存在很多细节。我的建议是，请你使用一个小的测试用例，比如包含 6 个节点，或者 7 个节点，或者 8 个节点的测试用例，实际去运行这个程序，用单步跟踪的方式去看，程序运行的过程中，每一步，各个变量在怎么变化，每个变量指向了哪个节点，每个节点的 next 又指向了哪个节点。在每一步链表变成了什么样子。
你可以使用纸笔去辅助，像课程 ppt 中的图示那样，画出整个链表的变化过程。去理解这个程序究竟是怎么运行的，为什么能正确的出回文（或者对于不是会问的情况，检测出他不是回文。）
继续加油！：）
022022-07-15
相似问题