Python实现单链表逆置

"单链表的逆置是一个常见的数据结构操作，主要涉及到链表的节点操作。通过遍历原链表，逐个调整节点的指向，可以实现链表的逆置。下面是一个Python语言实现单链表逆置的详细解释和代码示例。" 在计算机科学中，链表是一种线性数据结构，它由一系列节点组成，每个节点包含数据以及指向下一个节点的引用。单链表只具有指向下一个节点的指针，而没有指回上一个节点的指针。单链表的逆置操作就是改变链表中节点的顺序，使原来的头节点变为尾节点，原来的尾节点变为头节点。 逆置单链表的基本思想是使用三个指针：`prev`、`current`和`next_node`。初始时，`prev`指针为空，`current`指针指向链表的头节点。在遍历过程中，每次迭代都会执行以下步骤： 1. 保存`current`节点的下一个节点到`next_node`。 2. 将`current`节点的`next`指针指向`prev`，从而实现逆置。 3. 更新`prev`为`current`，使得`prev`始终指向当前处理的节点的前一个节点。 4. 更新`current`为`next_node`，继续处理下一个节点。 5. 当`current`为`None`时，遍历结束，此时`prev`就是新链表的头节点。 以下为详细代码解析： ```python class ListNode: def __init__(self, value=0, next=None): self.value = value self.next = next def reverse_linked_list(head): prev = None current = head # 遍历链表，逆置节点 while current is not None: next_node = current.next # 保存当前节点的下一个节点 current.next = prev # 将当前节点的指针指向前一个节点 prev = current # 更新前一个节点为当前节点 current = next_node # 更新当前节点为下一个节点 return prev # 返回新链表的头节点 # 示例用法 # 创建一个简单的链表：1->2->3->4->5 head = ListNode(1) head.next = ListNode(2) head.next.next = ListNode(3) head.next.next.next = ListNode(4) head.next.next.next.next = ListNode(5) # 逆置链表 new_head = reverse_linked_list(head) # 输出逆置后的链表：5->4->3->2->1 current = new_head while current is not None: print(current.value, end="->") current = current.next print("None") ``` 这段代码首先定义了一个`ListNode`类，用于创建链表节点。`reverse_linked_list`函数接受链表的头节点作为参数，然后按照上述策略进行逆置。最后，通过一个简单的例子展示了如何创建一个链表并调用逆置函数，然后打印出逆置后链表的元素。 逆置链表的这个方法的时间复杂度为O(n)，因为只需要遍历一次链表。空间复杂度为O(1)，因为只使用了常数个额外的指针，不依赖于输入链表的大小。这种方法是一种非常有效的链表操作技巧，常常在数据结构和算法面试中被问及。