链表逆序（链表逆序c语言）

链表逆序

简介

链表是一种重要的数据结构，它由一系列连接在一起的节点组成。每个节点存储一个值和指向下一个节点的链接。链表的逆序是将链表中的节点顺序反转。

如何逆序链表

逆序链表有两种主要方法：

迭代方法

1. 设置两个指针：`prev` 指向当前节点，`curr` 指向下一个节点。 2. 循环遍历链表，并在每次迭代中：- 将 `curr` 的 `next` 指针指向 `prev`。- 将 `prev` 移动到 `curr`。- 将 `curr` 移动到 `curr.next`。

递归方法

1. 如果链表为空或只有一个节点，则返回。 2. 递归逆序链表的剩余部分，得到一个新的头节点。 3. 设置当前节点的 `next` 指针指向 `null`。 4. 将新的头节点的 `next` 指针指向当前节点。 5. 返回新的头节点。

代码示例（迭代方法）

``` def reverse_list_iterative(head):prev = Nonecurr = headwhile curr:next_node = curr.nextcurr.next = prevprev = currcurr = next_nodereturn prev ```

代码示例（递归方法）

``` def reverse_list_recursive(head):if head is None or head.next is None:return headnew_head = reverse_list_recursive(head.next)head.next.next = headhead.next = Nonereturn new_head ```

复杂度分析

时间复杂度：

对于两种方法都是 O(n)，其中 n 是链表中的节点数量。

空间复杂度：

迭代方法是 O(1)，递归方法是 O(n)。

应用

链表逆序在各种应用中都有用处，例如：

将字符串倒置

计算数字的逆序

查找链表的中间节点

**链表逆序****简介**链表是一种重要的数据结构，它由一系列连接在一起的节点组成。每个节点存储一个值和指向下一个节点的链接。链表的逆序是将链表中的节点顺序反转。**如何逆序链表**逆序链表有两种主要方法：**迭代方法**1. 设置两个指针：`prev` 指向当前节点，`curr` 指向下一个节点。 2. 循环遍历链表，并在每次迭代中：- 将 `curr` 的 `next` 指针指向 `prev`。- 将 `prev` 移动到 `curr`。- 将 `curr` 移动到 `curr.next`。**递归方法**1. 如果链表为空或只有一个节点，则返回。 2. 递归逆序链表的剩余部分，得到一个新的头节点。 3. 设置当前节点的 `next` 指针指向 `null`。 4. 将新的头节点的 `next` 指针指向当前节点。 5. 返回新的头节点。**代码示例（迭代方法）**``` def reverse_list_iterative(head):prev = Nonecurr = headwhile curr:next_node = curr.nextcurr.next = prevprev = currcurr = next_nodereturn prev ```**代码示例（递归方法）**``` def reverse_list_recursive(head):if head is None or head.next is None:return headnew_head = reverse_list_recursive(head.next)head.next.next = headhead.next = Nonereturn new_head ```**复杂度分析*** **时间复杂度：**对于两种方法都是 O(n)，其中 n 是链表中的节点数量。 * **空间复杂度：**迭代方法是 O(1)，递归方法是 O(n)。**应用**链表逆序在各种应用中都有用处，例如：* 将字符串倒置 * 计算数字的逆序 * 查找链表的中间节点