链表检测回文串

Question

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

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逻辑有点懵逼 老师能够详细讲讲吗    

详细讲讲算法流程

Answer 1

liuyubobobo 2022-07-01 18:47:23

第一个红框的代码不仅仅将 slow 遍历到了链表 1/2 的位置，还把链表前半部分翻转了。所以，在第二个红框的部分，slow 在从链表的中间，向前遍历；prev 在从链表的中间，向后遍历。每次 slow 和 prev 指向的内容相同，才说明是回文串，否则就不是。

这里面存在很多细节。我的建议是，请你使用一个小的测试用例，比如包含 6 个节点，或者 7 个节点，或者 8 个节点的测试用例，实际去运行这个程序，用单步跟踪的方式去看，程序运行的过程中，每一步，各个变量在怎么变化，每个变量指向了哪个节点，每个节点的 next 又指向了哪个节点。在每一步链表变成了什么样子。

你可以使用纸笔去辅助，像课程 ppt 中的图示那样，画出整个链表的变化过程。去理解这个程序究竟是怎么运行的，为什么能正确的出回文（或者对于不是会问的情况，检测出他不是回文。）

继续加油！：）

• 提问者 慕粉3884565 #1

  我明白了实际上prev是倒序链表

• 提问者 慕粉3884565 #2

  非常感谢！