206. 反转链表

题目描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

出处：LeetCode

解法一：迭代

思路

我们可以使用迭代的方法来反转链表。我们定义两个指针 prev 和 curr，分别指向前一个节点和当前节点。然后我们遍历链表，每次迭代时，我们将当前节点的 next 指针指向前一个节点，然后将 prev 和 curr 向后移动一个节点。当 curr 为 null 时，说明链表已经反转完成，我们返回 prev 即可。

实现

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let curr: ListNode | null = head;

  while (curr !== null) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }

  return prev;
}

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

解法二：递归

思路

我们可以使用递归的方法来反转链表。我们定义一个递归函数 reverse，它接收一个节点 head 作为参数，返回反转后的链表。在递归函数中，我们首先判断 head 是否为 null，如果是，则直接返回 null；否则，我们递归调用 reverse 函数，传入 head.next 作为参数，得到反转后的链表 newHead。然后我们将 head.next 的 next 指针指向 head，并将 head.next 指向 null，最后返回 newHead。

实现

function reverseList(head: ListNode | null): ListNode | null {
  if (head === null || head.next === null) {
    return head;
  }

  const newHead = reverseList(head.next);
  head.next.next = head;
  head.next = null;

  return newHead;
}

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

解法三：栈

思路

我们可以使用栈来反转链表。我们可以将链表的节点依次入栈，然后出栈得到反转后的链表。

实现

function reverseList(head: ListNode | null): ListNode | null {
  const stack: ListNode[] = [];

  while (head !== null) {
    stack.push(head);
    head = head.next;
  }

  const dummy = new ListNode();
  let curr = dummy;

  while (stack.length > 0) {
    curr.next = stack.pop()!;
    curr = curr.next;
  }

  curr.next = null;

  return dummy.next;
}