206. 反转链表

**反转链表**

在计算机科学中，链表是一种常见的数据结构，它由一系列节点组成，每个节点包含一个值和一个指向下一个节点的引用。链表可以用于实现各种数据结构和算法。在本文中，我们将讨论如何反转一个链表。

**什么是反转链表**

反转链表是一种操作，通过改变链表中的每个节点的指针来使链表的顺序相反。例如，如果原链表为 A -> B -> C -> D，则反转后变为 D -> C -> B -> A。

**反转链表的方法**

有两种常见的方法可以实现反转链表：

1. **递归法**
2. **迭代法**

### 递归法递归法是通过递归函数来实现反转链表的。每次递归函数都会返回一个新的链表头部，直到整个链表都被反转。

class Node:
 def __init__(self, value):
 self.value = value self.next = Nonedef reverse_linked_list(head):
 """
 反转链表 :param head: 链表的头部节点 :return: 反转后的链表头部节点 """
 if not head or not head.next:
 return head new_head = reverse_linked_list(head.next)
 # 将原链表的最后一个节点指向新链表的头部 head.next.next = head head.next = None return new_head# 示例代码head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

new_head = reverse_linked_list(head)

while new_head:
 print(new_head.value, end=" ")
 new_head = new_head.next

def reverse_linked_list(head):
 """
 反转链表 :param head: 链表的头部节点 :return: 反转后的链表头部节点 """
 prev = None curr = head while curr:
 # 将原链表的最后一个节点指向新链表的头部 next_node = curr.next curr.next = prev # 移动到下一个节点 prev = curr curr = next_node return prev# 示例代码head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

new_head = reverse_linked_list(head)

while new_head:
 print(new_head.value, end=" ")
 new_head = new_head.next