好的，作为视觉专家，我仔细分析了您提供的图片。这是一道来自牛客网的经典算法题：**BM1 反转链表**。 题目要求给定一个单链表的头结点 `pHead`，将其反转后返回新的头结点。同时，对时间和空间复杂度有明确要求：时间复杂度 O(n)，空间复杂度 O(1)。 下面我将为您提供五种不同的 Python 解决方案，包括递归、迭代等主流方法，并附上详细的代码和注释。 首先，我们需要定义链表节点的数据结构，这是所有方案的基础。 ```python # 定义单链表节点类 class ListNode: def __init__(self, x): self.val = x self.next = None ``` --- ### 方案一：迭代法（三指针法）- 推荐 ✅ 这是最常用且高效的方法，完全符合题目 O(1) 空间复杂度的要求。它使用三个指针 (`prev`, `curr`, `next_temp`) 来逐个反转节点的指向。 **思路:** 1. 初始化 `prev` 为 `None`，`curr` 为头结点 `pHead`。 2. 在 `curr` 不为空的循环中： * 用 `next_temp` 暂存 `curr` 的下一个节点，防止断链。 * 将 `curr.next` 指向 `prev`，完成当前节点的反转。 * 将 `prev` 移动到 `curr` 的位置。 * 将 `curr` 移动到 `next_temp` 的位置，继续处理下一个节点。 3. 当循环结束时，`curr` 为 `None`，而 `prev` 正好指向新的头结点。 ```python def reverseList_iterative(pHead: ListNode) -> ListNode: """ 方案一：迭代法 (三指针) 时间复杂度: O(n) 空间复杂度: O(1) """ prev = None curr = pHead while curr: # 1. 暂存下一个节点 next_temp = curr.next # 2. 反转当前节点的指针 curr.next = prev # 3. 移动 prev 和 curr 指针 prev = curr curr = next_temp # 循环结束后，prev 指向新的头结点 return prev ``` --- ### 方案二：递归法 递归法的思想非常优雅，但会占用 O(n) 的栈空间，不完全符合题目 O(1) 空间复杂度的最优要求，但在面试中是考察递归思维的常见题型。 **思路:** 1. **终止条件**: 如果当前节点 `pHead` 为空或只有一个节点 (`pHead.next` 为空)，则直接返回 `pHead`，因为它本身就是反转后的头结点。 2. **递归调用**: 对 `pHead.next` 进行递归，得到子链表反转后的新头结点 `new_head`。此时，从 `pHead.next` 开始的链表已经被反转。 3. **反转连接**: 将 `pHead.next` (现在是子链表的尾节点) 的 `next` 指针指向 `pHead`。 4. **断开旧连接**: 将 `pHead.next` 设为 `None`，防止形成环。 5. **返回结果**: 返回 `new_head`。 ```python def reverseList_recursive(pHead: ListNode) -> ListNode: """ 方案二：递归法 时间复杂度: O(n) 空间复杂度: O(n) (由于递归调用栈) """ # 基本情况：空链表或只有一个节点 if not pHead or not pHead.next: return pHead # 递归反转剩余部分，new_head 是反转后链表的头 new_head = reverseList_recursive(pHead.next) # 关键步骤：将当前节点的下一个节点的 next 指向自己 pHead.next.next = pHead # 断开原来的连接，避免成环 pHead.next = None return new_head ``` --- ### 方案三：头插法 这种方法通过创建一个虚拟头结点 `dummy`，然后遍历原链表，将每个节点依次“插入”到 `dummy` 之后。最终，`dummy.next` 就是反转后的链表头。 **思路:** 1. 创建一个虚拟头结点 `dummy`，其 `next` 初始为 `None`。 2. 遍历原链表，对于每个节点 `curr`： * 暂存 `curr` 的下一个节点 `next_temp`。 * 将 `curr` 插入到 `dummy` 和 `dummy.next` 之间。即 `curr.next = dummy.next`，然后 `dummy.next = curr`。 3. 遍历完成后，`dummy.next` 即为新链表的头。 ```python def reverseList_head_insertion(pHead: ListNode) -> ListNode: """ 方案三：头插法 时间复杂度: O(n) 空间复杂度: O(1) """ dummy = ListNode(0) # 虚拟头结点 curr = pHead while curr: next_temp = curr.next # 暂存下一个节点 # 将 curr 插入到 dummy 之后 curr.next = dummy.next dummy.next = curr curr = next_temp # 移动到下一个节点 return dummy.next ``` --- ### 方案四：使用栈 (Stack) 这种方法利用了栈“后进先出”(LIFO) 的特性。虽然直观，但需要 O(n) 的额外空间来存储节点，不符合 O(1) 空间复杂度的要求。 **思路:** 1. 遍历原链表，将所有节点压入一个栈中。 2. 弹出栈顶元素作为新链表的头结点 `new_head`。 3. 持续从栈中弹出节点，并将其连接到前一个节点的 `next` 上。 4. 最后，确保新链表尾节点的 `next` 指向 `None`。 ```python def reverseList_stack(pHead: ListNode) -> ListNode: """ 方案四：使用栈 时间复杂度: O(n) 空间复杂度: O(n) """ if not pHead: return None stack = [] curr = pHead # 1. 将所有节点压入栈 while curr: stack.append(curr) curr = curr.next # 2. 弹出栈顶作为新头结点 new_head = stack.pop() curr = new_head # 3. 依次连接栈中剩余节点 while stack: node = stack.pop() curr.next = node curr = node # 4. 最后一个节点的 next 必须设为 None curr.next = None return new_head ``` --- ### 方案五：双指针简化版 这是对方案一（三指针法）的一种更简洁的写法，本质相同，只是变量命名和逻辑组织略有不同，同样满足 O(1) 空间复杂度。 **思路:** 1. 定义两个指针 `prev` (初始为 `None`) 和 `curr` (初始为 `pHead`)。 2. 在 `curr` 不为空时循环： * 同时更新 `curr.next`, `prev`, `curr` 的值。`curr.next` 指向 `prev`，`prev` 变为当前的 `curr`，`curr` 变为原来的 `curr.next`。 3. 返回 `prev`。 ```python def reverseList_two_pointers(pHead: ListNode) -> ListNode: """ 方案五：双指针简化版 时间复杂度: O(n) 空间复杂度: O(1) """ prev = None curr = pHead while curr: # Python 的多重赋值可以一行完成三步操作 # 等价于: # next_temp = curr.next # curr.next = prev # prev = curr # curr = next_temp curr.next, prev, curr = prev, curr, curr.next return prev ``` ### 总结与测试 以上五种方案都能正确反转链表。根据题目要求 **空间复杂度 O(1)**，**方案一、方案三和方案五** 是最优解。其中，**方案一（三指针法）** 是最经典、最易理解且被广泛采用的方法。 您可以使用以下代码来测试这些函数： ```python # --- 测试代码 --- def create_linked_list(values): """辅助函数：根据列表创建链表""" if not values: return None head = ListNode(values[0]) current = head for val in values[1:]: current.next = ListNode(val) current = current.next return head def print_linked_list(head): """辅助函数：打印链表""" values = [] current = head while current: values.append(str(current.val)) current = current.next print("->".join(values)) # 创建测试链表 1 -> 2 -> 3 head = create_linked_list([1, 2, 3]) print("原始链表:") print_linked_list(head) # 测试方案一 reversed_head_1 = reverseList_iterative(head) print("\n方案一 (迭代法) 反转后:") print_linked_list(reversed_head_1) # 重新创建链表用于测试其他方案 head = create_linked_list([1, 2, 3]) # 测试方案二 reversed_head_2 = reverseList_recursive(head) print("\n方案二 (递归法) 反转后:") print_linked_list(reversed_head_2) # ... 您可以类似地测试其他方案 ```