反转单向链表（反转单链表 三种方法整理）

## 反转单向链表### 简介反转单向链表是一个常见的算法问题，它要求将一个单向链表的节点顺序反转。例如，给定一个链表 1 -> 2 -> 3 -> 4 -> 5，反转后应该变为 5 -> 4 -> 3 -> 2 -> 1。### 算法思路反转链表的常见思路是使用三个指针：

prev

: 指向当前节点的前一个节点

curr

: 指向当前节点

next

: 指向当前节点的下一个节点算法的步骤如下：1. 初始化三个指针：`prev = None`, `curr = head`, `next = None`。 2. 循环遍历链表，直到 `curr` 指向 `None`：- 将 `curr` 的 `next` 指针指向 `prev`，反转当前节点的指向。- 将 `prev` 指针移动到 `curr`。- 将 `curr` 指针移动到 `next`。 3. 返回 `prev`，它指向反转后的链表头节点。### 代码实现```python class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef reverseList(head):prev = Nonecurr = headwhile curr:next = curr.nextcurr.next = prevprev = currcurr = nextreturn prev ```### 代码解释1. 首先定义一个 `ListNode` 类，用来表示链表中的节点。 2. `reverseList` 函数接受一个链表的头节点 `head` 作为输入。 3. 初始化三个指针：`prev = None`, `curr = head`, `next = None`。 4. 使用 `while` 循环遍历链表，直到 `curr` 指向 `None`。 5. 在循环体中，首先将 `curr` 的 `next` 指针指向 `prev`，反转当前节点的指向。 6. 然后将 `prev` 指针移动到 `curr`。 7. 最后将 `curr` 指针移动到 `next`，继续遍历下一个节点。 8. 循环结束后，`prev` 指针指向反转后的链表头节点，因此返回 `prev`。### 总结反转单向链表是一个经典的算法问题，其思路是通过三个指针进行遍历和反转。代码实现简单易懂，可以有效地解决问题。### 拓展除了上述的迭代方法，还可以使用递归方法来实现反转链表。递归方法更加简洁，但可能不太容易理解。```python def reverseList_recursive(head):if not head or not head.next:return headnew_head = reverseList_recursive(head.next)head.next.next = headhead.next = Nonereturn new_head ```### 注意事项

链表的反转会改变原链表的结构。

需要注意处理空链表和只有一个节点的链表的情况。### 总结反转单向链表是一个非常基础且常见的算法问题，通过理解其思路和实现方法，可以更好地掌握链表操作的相关知识。

反转单向链表

简介反转单向链表是一个常见的算法问题，它要求将一个单向链表的节点顺序反转。例如，给定一个链表 1 -> 2 -> 3 -> 4 -> 5，反转后应该变为 5 -> 4 -> 3 -> 2 -> 1。

算法思路反转链表的常见思路是使用三个指针：* **prev**: 指向当前节点的前一个节点 * **curr**: 指向当前节点 * **next**: 指向当前节点的下一个节点算法的步骤如下：1. 初始化三个指针：`prev = None`, `curr = head`, `next = None`。 2. 循环遍历链表，直到 `curr` 指向 `None`：- 将 `curr` 的 `next` 指针指向 `prev`，反转当前节点的指向。- 将 `prev` 指针移动到 `curr`。- 将 `curr` 指针移动到 `next`。 3. 返回 `prev`，它指向反转后的链表头节点。

代码实现```python class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef reverseList(head):prev = Nonecurr = headwhile curr:next = curr.nextcurr.next = prevprev = currcurr = nextreturn prev ```

代码解释1. 首先定义一个 `ListNode` 类，用来表示链表中的节点。 2. `reverseList` 函数接受一个链表的头节点 `head` 作为输入。 3. 初始化三个指针：`prev = None`, `curr = head`, `next = None`。 4. 使用 `while` 循环遍历链表，直到 `curr` 指向 `None`。 5. 在循环体中，首先将 `curr` 的 `next` 指针指向 `prev`，反转当前节点的指向。 6. 然后将 `prev` 指针移动到 `curr`。 7. 最后将 `curr` 指针移动到 `next`，继续遍历下一个节点。 8. 循环结束后，`prev` 指针指向反转后的链表头节点，因此返回 `prev`。

总结反转单向链表是一个经典的算法问题，其思路是通过三个指针进行遍历和反转。代码实现简单易懂，可以有效地解决问题。

拓展除了上述的迭代方法，还可以使用递归方法来实现反转链表。递归方法更加简洁，但可能不太容易理解。```python def reverseList_recursive(head):if not head or not head.next:return headnew_head = reverseList_recursive(head.next)head.next.next = headhead.next = Nonereturn new_head ```

注意事项* 链表的反转会改变原链表的结构。 * 需要注意处理空链表和只有一个节点的链表的情况。

总结反转单向链表是一个非常基础且常见的算法问题，通过理解其思路和实现方法，可以更好地掌握链表操作的相关知识。