js实现反转链表的两种方法

**反转链表的两种方法**

在 JavaScript 中，链表是一种常见的数据结构，它由一个个节点组成，每个节点包含一个值和一个指向下一个节点的引用。链表可以用来实现各种算法和数据结构，如栈、队列等。在本文中，我们将讨论如何反转一个链表，及其两种不同的实现方法。

**反转链表的定义**

反转链表是指将链表中的所有节点按照逆序排列。例如，如果原链表为 `1 ->2 ->3 ->4 ->5`,则反转后的链表为 `5 ->4 ->3 ->2 ->1`。

**方法一：迭代法**

首先，我们来看一下迭代法的实现。这个方法通过将每个节点的 next 指针指向其前一个节点来实现反转。

javascriptclass Node {
 constructor(x) {
 this.val = x;
 this.next = null;
 }
}

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

 while (curr !== null) {
 //保存下一个节点的引用 const nextNode = curr.next;

 // 将当前节点的 next 指针指向其前一个节点 curr.next = prev;

 // 移动到下一个节点 prev = curr;
 curr = nextNode;
 }

 return prev; // 返回反转后的链表头部}

在这个实现中，我们使用三个变量来跟踪当前的链表：`prev`、`curr` 和 `nextNode`。我们首先将 `head` 赋值给 `curr`，然后进入一个循环直到 `curr` 为 null。

在每次迭代中，我们保存下一个节点的引用（即 `curr.next`)，然后将当前节点的 next 指针指向其前一个节点（即 `prev`)。最后，我们移动到下一个节点（即 `nextNode`)。

循环结束后，我们返回 `prev`，因为它现在指向了反转后的链表头部。

**方法二：递归法**

接下来，我们来看一下递归法的实现。这个方法通过将每个子链表反转，然后合并它们来实现反转。

javascriptfunction reverseList(head) {
 if (head === null || head.next === null) {
 return head; // 如果链表只有一个节点或没有节点，则返回原链表 }

 const newHead = reverseList(head.next); // 反转后续的子链表 head.next.next = head; // 将当前节点的 next 指针指向其前一个节点 head.next = null; // 将当前节点的 next 指针置为 null return newHead; // 返回反转后的链表头部}

在这个实现中，我们首先检查链表是否只有一个节点或没有节点。如果是，则直接返回原链表。

否则，我们递归地反转后续的子链表（即 `head.next`)，并将其赋值给 `newHead`。

然后，我们将当前节点的 next 指针指向其前一个节点（即 `head.next = head`），并将当前节点的 next 指针置为 null。

最后，我们返回 `newHead`，因为它现在指向了反转后的链表头部。

**总结**

在本文中，我们讨论了如何反转一个链表，以及其两种不同的实现方法：迭代法和递归法。迭代法通过将每个节点的 next 指针指向其前一个节点来实现反转，而递归法则通过将每个子链表反转，然后合并它们来实现反转。

这两个方法都可以用来实现链表的反转功能，选择哪种方法取决于具体的需求和场景。