BM13 判断一个链表是否为回文结构

题目描述

思路分析

• 将链表分成两段，最后进行节点的比对
• 问题：
  • 将链表均分为两端，可以使用快慢指针的方法，当fast指针运动到最后时，slow指针刚好到中点
  • 对于链表长度为奇数或是偶数时要做不同的处理
    -将后面一段链表进行反转，可以使用之前的反转链表部分的代码

代码参考

function isPail (head) {
  if (!head || !head.next) return true
  // write code here
  // 使用快慢指针找到链表的中间节点
  let fast = slow = head
  let first = second = null
  while (fast.next != null && fast.next.next != null) {
    fast = fast.next.next
    slow = slow.next
  }
  // 如果为奇数个，那么此时slow执行最中间的那个，
  // 如果为偶数个，那么此时slow指向中间的前一个
  // fast的next不为null，则为偶数个
  if (fast.next != null) {
    // 比如 1 2 3 4 5 6 此时 fast指向5，slow指向3
    first = slow.next
    // 将slow的next置空，也就是断开链表
    slow.next = null
    second = head
  } else {
    // 如果fast的next为null，则说明它是奇数个，比如1 2 3 4 5 fast指向5，slow为3
    first = slow.next
    // 此时我们需要裁成 1-2  4-5,也就是要找到slow的前驱结点
    // 找到slow的前驱结点pre
    let pre = head
    while (pre.next != slow) {
      pre = pre.next
    }
    // 将pre的next置为null，此时从head遍历结果为1-2
    pre.next = null
    second = head
  }

  first = reverseList(first)
  // 进行两条链表的比对
  while (first) {
    if (first.val != second.val) return false
    first = first.next
    second = second.next
  }
  return true

}
// 链表反转
const reverseList = (head) => {
  if (head == null) return head
  let pre = null, cur = head
  while (cur) {
    let temp = cur.next
    cur.next = pre
    pre = cur
    cur = temp
  }
  return pre
}