首页python 链表反转

python 链表反转

时间: 2025-04-22 15:00:15 浏览: 37

### 链表反转算法的Python实现 #### 迭代方式实现链表反转定义单向链表节点类 `ListNode` 如下： ```python class ListNode: def __init__(self, x): self.val = x self.next = None ``` 为了使用迭代的方式反转链表，可以创建一个新的函数 `reverseList_iterative` 来处理这个问题。此方法会遍历整个列表一次，并逐步改变指针的方向。 ```python def reverseList_iterative(head): prev = None current = head while current is not None: next_node = current.next # 记录下一个节点 current.next = prev # 改变当前节点指向方向 prev = current # 移动prev到当前位置 current = next_node # 继续访问下一个位置 return prev # 返回新的头结点 ``` 这种方法的时间复杂度为 O(n)[^1] ，因为需要线性时间来遍历所有元素；同时由于只用了几个额外变量存储临时数据，所以其空间复杂度为 O(1)[^2]。 #### 使用递归的方法实现链表反转除了迭代外，还可以采用递归来完成同样的任务。下面是一个简单的例子展示了如何利用递归特性来进行链表反转操作: ```python def reverseList_recursive(head): if (head == None or head.next == None): return head p = reverseList_recursive(head.next) head.next.next = head head.next = None return p ``` 这段代码同样实现了链表反转的功能，在每次调用自身时都会深入一层直到遇到最后一个节点为止，之后再逐层返回并调整各节点之间的连接关系。

阅读全文