#回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2]
输出：false

提示：

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

进阶：

你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

#解题思路

题目信息：回文

#思路一

遍历时放入数组，数组从两边开始对比，时间复杂度 O(n)，空间复杂度 O(n)

#思路二

需要空间复杂度 O(1)，遍历第一遍记录长度，遍历第二遍双指针从中间开始判断是否回文，并且需要反转前半链表

#首次代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function isPalindrome(head: ListNode | null): boolean {
  let length = 0

  let i = head,
    j = head,
    k = head

  while (i) {
    length++
    i = i.next
  }

  let l = Math.ceil(length / 2)

  while (l) {
    if (l === (length % 2) + 1) {
      let m = k
      k = k.next
      m.next = null
      m = null
    } else {
      k = k.next
    }

    l--
  }

  console.log(j, k)
  j = reverseList(j)
  console.log(j, k)

  while (k) {
    if (k.val !== j.val) {
      return false
    }
    k = k.next
    j = j.next
  }

  return true
}

function reverseList(head: ListNode | null): ListNode | null {
  let pre = null
  let cur = head
  let t = null

  while (cur) {
    t = cur.next
    cur.next = pre

    pre = cur
    cur = t
  }

  return pre
}