首页6-2 Reverse Linked List 6-2 反向链表

6-2 Reverse Linked List 6-2 反向链表

时间: 2025-06-28 11:22:38 浏览: 13

### 如何反转链表在编程中，反转单向链表是一个常见的操作。下面将介绍一种迭代方法来实现这一功能。 #### 迭代法反转链表通过创建三个指针变量 `prev`、`current` 和 `next` 来逐步遍历并翻转节点之间的指向关系[^1]： ```python class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def reverse_linked_list(head: ListNode) -> ListNode: prev = None current = head while current is not None: next_node = current.next # Store reference to next node before changing it. current.next = prev # Reverse link direction. prev = current # Move previous pointer forward one step. current = next_node # Move current pointer forward one step. return prev # New head of reversed list will be last non-null 'prev'. ``` 此算法的时间复杂度为 O(n)，其中 n 是列表中的元素数量；空间复杂度为 O(1)，因为它只使用固定额外内存完成任务。为了更好地理解上述过程的工作原理，考虑如下图所示的一个简单例子，在每一步之后展示了各个指针的状态变化情况。初始状态： ``` NULL <- A -> B -> C -> D -> NULL prev curr next ``` 第一次循环结束后的状态： ``` NULL <- A <-> B -> C -> D -> NULL prev curr next ``` 第二次循环结束后： ``` NULL <- A <- B <-> C -> D -> NULL prev curr next ``` 最终结果将是所有箭头方向都被逆转过来，形成一个新的从D到A的链接序列。

阅读全文