反转链表（LeetCode206）

反转链表

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

问题描述

给定一个单链表，需要将其反转，使链表的每个节点指向它的前一个节点，最终使链表的尾节点成为新的头节点。

方法1：使用栈

使用栈是一种简单且直观的方式来反转链表。我们可以通过将链表节点依次压入栈中，然后再弹出栈来实现链表的反转。

实现步骤：

1. 如果链表为空或只有一个节点，直接返回。
2. 创建一个栈，用于存储链表节点。
3. 遍历链表，将节点依次压入栈中。
4. 取出栈顶节点作为新链表的头节点。
5. 依次弹出栈中的节点，连接成新的链表。
6. 将尾节点的 指针置空，确保新链表的结束。

代码实现：

const reverseList = function (head) {
  if (!head || !head.next) return head; // 如果链表为空或只有一个节点，直接返回

  const stack = []; // 创建一个栈

  // 遍历链表，将节点依次压入栈中
  let current = head;
  while (current !== null) {
    stack.push(current);
    current = current.next;
  }

  const newHead = stack.pop(); // 取出栈顶节点作为新链表的头节点
  let newCurrent = newHead;

  // 依次弹出栈中的节点，连接成新的链表
  while (stack.length > 0) {
    newCurrent.next = stack.pop();
    newCurrent = newCurrent.next;
  }

  newCurrent.next = null; // 尾节点的 next 指针置空，确保新链表的结束

  return newHead; // 返回新链表的头节点
};

方法2：迭代法

迭代法通过逐步反转节点的 next 指针来实现链表反转。 我们使用三个指针来追踪当前节点及其前后节点。

实现步骤：

1. 初始化 prev 为 null，current 为头节点。
2. 遍历链表，对于每个节点，将 current.next 指向 prev。
3. 更新 prev 和 current 指针，继续遍历直到链表结束。
4. 最终，prev 将成为新的头节点。

代码实现：

const reverseList = function(head) {
  let prev = null;
  let current = head;
  while (current !== null) {
      const nextTemp = current.next;
      current.next = prev;
      prev = current;
      current = nextTemp;
  }
  return prev;
};

方法3：递归法

递归方法通过将问题拆解为更小的子问题来解决。我们递归地反转子链表，然后调整当前节点的指针。

实现步骤：

1. 如果链表为空或只有一个节点，直接返回。
2. 递归反转子链表，获取新的头节点。
3. 调整当前节点的指针，使其指向前一个节点。
4. 返回新的头节点。

代码实现：

const reverseList = function (head) {
  if (head == null || head.next === null) return head;
  const rList = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return rList;
};

总结

本文介绍了三种反转单链表的方法：使用栈、迭代法和递归法。每种方法都有其独特的实现方式和适用场景。使用栈的方法比较直观，适合理解数据结构的基本操作；迭代法在时间和空间效率上较为优越；递归法则更为简洁和优雅，但需要注意递归深度问题。通过对比和实践，选择适合自己需求的实现方法。