链表的反转（链表反转c++代码）

## 链表的反转### 简介链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的反转是指将链表的节点顺序反转，使得最后一个节点成为新的头节点，而第一个节点成为新的尾节点。### 1. 链表反转的意义链表反转在数据结构和算法中有着重要的应用，例如：

栈和队列的实现:

链表可以用来实现栈和队列，而链表的反转可以用于实现栈的出栈操作或队列的入队操作。

逆序遍历:

链表反转可以实现对链表的逆序遍历，例如，从链表的尾部开始依次访问每个节点。

算法优化:

在某些算法中，链表反转可以简化代码实现或提高算法效率。### 2. 链表反转的实现方法链表反转的主要方法有两种：#### 2.1 迭代法迭代法是最常用的链表反转方法，它通过循环遍历链表，逐个反转节点的指针。具体步骤如下：1. 初始化三个指针：`prev` 指向 null，`curr` 指向链表的头节点，`next` 指向下一个节点。 2. 遍历链表，直到 `curr` 指向 null。 3. 在循环中，将 `curr` 指向 `next` 节点的 `next` 指针。 4. 将 `curr` 的 `next` 指针指向 `prev` 节点。 5. 更新 `prev` 和 `curr` 指针，`prev` 指向 `curr`，`curr` 指向 `next`。

代码示例 (Python):

```python class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef reverse_linked_list(head):prev = Nonecurr = headwhile curr:next = curr.nextcurr.next = prevprev = currcurr = nextreturn prev ```#### 2.2 递归法递归法利用递归调用来反转链表。具体步骤如下：1. 递归的基线条件：当链表为空或只有一个节点时，直接返回 head。 2. 递归调用：将 `head` 节点的 `next` 节点作为新的 `head`，递归调用 `reverse_linked_list` 函数。 3. 反转指针：将 `head.next` 指针指向当前 `head` 节点。 4. 返回新的 `head` 节点。

代码示例 (Python):

```python class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef reverse_linked_list(head):if not head or not head.next:return headnew_head = reverse_linked_list(head.next)head.next.next = headhead.next = Nonereturn new_head ```### 3. 链表反转的复杂度分析

时间复杂度:

两种方法的时间复杂度都是 O(n)，其中 n 是链表的节点数量。

空间复杂度:

迭代法没有额外的空间开销，空间复杂度为 O(1)。递归法需要额外的栈空间来保存递归调用信息，空间复杂度为 O(n)，但实际情况下，递归深度不会超过链表的长度。### 4. 总结链表的反转是数据结构和算法中一个重要的操作，它可以用于多种应用场景。迭代法和递归法是两种常用的反转方法，它们各有优缺点。根据实际情况选择最适合的方法。

链表的反转

简介链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的反转是指将链表的节点顺序反转，使得最后一个节点成为新的头节点，而第一个节点成为新的尾节点。

1. 链表反转的意义链表反转在数据结构和算法中有着重要的应用，例如：* **栈和队列的实现:** 链表可以用来实现栈和队列，而链表的反转可以用于实现栈的出栈操作或队列的入队操作。 * **逆序遍历:** 链表反转可以实现对链表的逆序遍历，例如，从链表的尾部开始依次访问每个节点。 * **算法优化:** 在某些算法中，链表反转可以简化代码实现或提高算法效率。

2. 链表反转的实现方法链表反转的主要方法有两种：

2.1 迭代法迭代法是最常用的链表反转方法，它通过循环遍历链表，逐个反转节点的指针。具体步骤如下：1. 初始化三个指针：`prev` 指向 null，`curr` 指向链表的头节点，`next` 指向下一个节点。 2. 遍历链表，直到 `curr` 指向 null。 3. 在循环中，将 `curr` 指向 `next` 节点的 `next` 指针。 4. 将 `curr` 的 `next` 指针指向 `prev` 节点。 5. 更新 `prev` 和 `curr` 指针，`prev` 指向 `curr`，`curr` 指向 `next`。**代码示例 (Python):**```python class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef reverse_linked_list(head):prev = Nonecurr = headwhile curr:next = curr.nextcurr.next = prevprev = currcurr = nextreturn prev ```

2.2 递归法递归法利用递归调用来反转链表。具体步骤如下：1. 递归的基线条件：当链表为空或只有一个节点时，直接返回 head。 2. 递归调用：将 `head` 节点的 `next` 节点作为新的 `head`，递归调用 `reverse_linked_list` 函数。 3. 反转指针：将 `head.next` 指针指向当前 `head` 节点。 4. 返回新的 `head` 节点。**代码示例 (Python):**```python class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef reverse_linked_list(head):if not head or not head.next:return headnew_head = reverse_linked_list(head.next)head.next.next = headhead.next = Nonereturn new_head ```

3. 链表反转的复杂度分析* **时间复杂度:** 两种方法的时间复杂度都是 O(n)，其中 n 是链表的节点数量。 * **空间复杂度:** 迭代法没有额外的空间开销，空间复杂度为 O(1)。递归法需要额外的栈空间来保存递归调用信息，空间复杂度为 O(n)，但实际情况下，递归深度不会超过链表的长度。

4. 总结链表的反转是数据结构和算法中一个重要的操作，它可以用于多种应用场景。迭代法和递归法是两种常用的反转方法，它们各有优缺点。根据实际情况选择最适合的方法。