链表的基本操作-526互联

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)
  }
}

/**
 * 数组转链表
 * @param arr
 * @param index
 */
function arrayToList(arr: number[], index: number): ListNode | null {
  if (arr[index]) {
    return new ListNode(arr[index], arrayToList(arr, index + 1))
  } else {
    return null
  }
}

/**
 * 遍历链表
 * @param list
 */
function ergodicList(list: ListNode | null) {
  while (list) {
    console.log(list.val)
    list = list.next
  }
}

/**
 * 反转链表
 * @param list
 */
function reverseList(list: ListNode | null): ListNode | null {
  let head = null
  while (list) {
    const next = list.next
    list.next = head
    head = list
    list = next
  }
  return head
}

/**
 * 力扣：回文链表
 * @param head
 */
function isPalindrome(head: ListNode | null): boolean {
  // 快慢指针遍历
  let fast: ListNode | null = head, slow: ListNode | null = head
  while (fast && fast.next) {
    slow = slow!.next
    fast = fast.next.next
  }
  // 反转后半部分链表
  let afterHead = reverseList(slow)
  // 遍历反转后的链表并比对
  while (afterHead) {
    if (head!.val !== afterHead!.val) {
      return false
    }
    head = head!.next
    afterHead = afterHead.next
  }
  return true
};

const list = arrayToList([], 0)

console.log(isPalindrome(list))