Lstmxx的空间

链表的遍历方式

递归

整个链表反转

const reverse = function (head: ListNode): ListNode {
  if (head.next === null) {
    return head
  }
  const last: ListNode = reverse(head.next)
  head.next.next = head
  head.next = null
  return last
}

链表 n 个反转

const reverse = (function () {
  let back = null
  return function (head: ListNode, right: number): ListNode {
    if (right === 1) {
      back = head.next
      return head
    }
    const last: ListNode = reverse(head.next, right - 1)
    head.next.next = head
    head.next = back
    return last
  }
})()

链表其实也是树的一种

function traverse(head: ListNode | null) {
  // 前序遍历代码
  traverse(head.next)
  // 后序遍历代码
}

迭代

反转链表

const reverse = function(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
}

快慢指针找链表中点

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
}