206.反转链表.md

206.反转链表

/*
 * @lc app=leetcode.cn id=206 lang=typescript
 *
 * [206] 反转链表
 */

// @lc code=start
/**
 * 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)
 *     }
 * }
 */

interface ListNode {
  val: number
  next: ListNode | null
}

function reverseList(head: ListNode | null): ListNode | null {}
// @lc code=end

解法 1: 双指针

• 时间复杂度:
• 空间复杂度:

使用两个变量保存当前结点和下一个结点,每次迭代将下一个结点指向当前结点

function reverseList(head: ListNode | null): ListNode | null {
  let current = null
  let next = head
  while (next) {
    let temp = next.next
    next.next = current
    current = next
    next = temp
  }
  return current
}

解法 2: 使用外部数组

• 时间复杂度:
• 空间复杂度:

遍历所有结点,保存到一个数组中,反转数组,再一个个修改元素的 next 指针

function reverseList(head: ListNode | null): ListNode | null {
  let tmpArr: [null, ...Array<ListNode>] = [null]
  let cur = head
  while (cur) {
    tmpArr.push(cur)
    cur = cur.next
  }
  for (let i = tmpArr.length - 1; i > 0; i--) {
    tmpArr[i]!.next = tmpArr[i - 1]
  }
  return tmpArr[tmpArr.length - 1]
}

解法 3: 递归

• 时间复杂度:
• 空间复杂度:

function reverseList(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return head

  let next = reverseList(head.next)
  head.next.next = head
  head.next = null
  return next
}

尾递归优化

• 时间复杂度:
• 空间复杂度:

function reverseList(head: ListNode | null, pre: ListNode | null = null): ListNode | null {
  if (!head) return pre

  const next = head.next
  head.next = pre
  return reverseList(next, head)
}

解法 4: 妖魔化的双指针

• https://leetcode-cn.com/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-shuang-zhi-zhen-di-gui-yao-mo-/

function reverseList(head: ListNode | null): ListNode | null {
  let pre = head
  while (head && head.next) {
    const next = head.next
    head.next = next.next
    next.next = pre
    if (!head.next) return next

    pre = next
  }
  return head
}

CASE

test.each([
  { input: { head: [1, 2, 3, 4, 5] }, output: [5, 4, 3, 2, 1] },
  { input: { head: [1, 2] }, output: [2, 1] },
  { input: { head: [] }, output: [] },
])('input: head = $input.head', ({ input: { head }, output }) => {
  const root = LinkedList.deserialize(head)
  const res = reverseList(root)
  expect(LinkedList.serialize(res)).toEqual(output)
})