链表检测回文串

Question

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

  非常感谢！