Lstmxx的空间

234. 回文链表

请判断一个链表是否为回文链表。

链接

递归

空间复杂度O(n)。因为每一次都要压栈，所以要遍历完整个链表。

function isPalindrome(head: ListNode | null): boolean {
  let left = head
  function traverse(right: ListNode | null) {
    if (right === null) return true
    let res = traverse(right.next)
    res = res && (left.val === right.val)
    left = left.next
    return res
  }
  return traverse(head)
}

迭代

function isPalindrome(head: ListNode | null): boolean {
  let mid = findMid(head)
  let left = head
  let right = resverse(mid)
  let last = right
  let leftLast = null
  while(right != null) {
    if (left.val !== right.val) return false
    leftLast = left
    left = left.next
    right = right.next
  }
  leftLast && (leftLast.next = resverse(last)) // 还原链表
  return true
}

function findMid(head: ListNode): ListNode {
  let slow = head, fast = head
  while(fast != null && fast.next != null) {
    slow = slow.next
    fast = fast.next.next
  }
  if (fast !== null) slow = slow.next
  return slow
}

function resverse(head: ListNode): ListNode {
  let pre = null
  let cur = head
  let next = null
  while(cur !== null) {
    next = cur.next
    cur.next = pre
    pre = cur
    cur = next
  }
  return pre
}