算法通关村第二关——终于学会链表反转了

**算法通关村第二关——链表反转**

在前面的第一关中，我们学习了如何使用栈来实现链表的反转。虽然我们成功地完成了这个任务，但是我们的解决方案可能还不是最优的。因此，在本关中，我们将继续深入探讨链表反转的算法。

**链表反转的基本概念**

链表是一种常见的数据结构，它由一系列的结点组成，每个结点包含一个值和一个指向下一个结点的引用。链表反转是指将链表中的结点顺序颠倒，形成新的链表。

**链表反转的算法**

有两种常见的链表反转算法：递归反转和迭代反转。

### 递归反转递归反转是一种使用函数递归来实现链表反转的方法。下面是递归反转的示例代码：

class Node:
 def __init__(self, value):
 self.value = value self.next = Nonedef reverse(head):
 if head is None or head.next is None:
 return head new_head = reverse(head.next)
 head.next.next = head head.next = None return new_head

在这个示例中，我们定义了一个 `reverse` 函数，它将链表反转为新的链表。函数的基本逻辑是：

1. 如果链表为空或只有一个结点，则返回原链表。
2. 否则，将链表的下一个结点作为新链表的头结点，反转剩余链表。
3. 将当前结点作为新链表的尾结点。

### 迭代反转迭代反转是一种使用循环来实现链表反转的方法。下面是迭代反转的示例代码：

class Node:
 def __init__(self, value):
 self.value = value self.next = Nonedef reverse(head):
 prev = None curr = head while curr is not None:
 next_node = curr.next curr.next = prev prev = curr curr = next_node return prev

在这个示例中，我们定义了一个 `reverse` 函数，它将链表反转为新的链表。函数的基本逻辑是：

1. 初始化三个指针： `prev`、`curr` 和 `next_node`，分别指向原链表的前驱结点、当前结点和下一个结点。
2. 循环遍历链表，直到 `curr` 指向空结点。
3. 在每次循环中，将 `curr` 结点的 `next` 指针指向 `prev` 结点，更新 `prev` 和 `curr` 指针。

**总结**

在本关中，我们学习了链表反转的基本概念和两种常见的算法：递归反转和迭代反转。我们通过示例代码来理解每种算法的逻辑，并且可以根据需要选择最合适的解决方案。

**参考**

* [链表反转]( />* [递归反转]( />* [迭代反转](