Python实现单链表反转的三种核心算法详解
本文详细解析Python中单链表反转的三种主流实现方式：头部删除与插入法、三指针迭代法以及递归法。文章结合Node与LinkedList类定义，逐步演示各算法的逻辑步骤、指针移动过程及代码实现，涵盖从基础概念到具体编码的全流程，适用于准备大厂算法面试的开发者参考。
当前大厂技术面试中，算法题已成为必考环节，且难度逐年提升，不再局限于简单的列表或字符串操作，而是深入考察各类数据结构的应用。其中，单链表的反转是高频考查的经典题目，本文对此进行整理记录，以便深入理解。
1. 链表的基本特性：
链表采用顺序存储逻辑，但物理空间上元素并不连续。因此，每个节点除了存储实际数据值外，还需存储指向下一个节点的地址（指针）。单链表仅包含指向后继节点的指针，而双向链表则额外包含指向前驱节点的指针。得益于这种存储结构，链表在执行插入和删除操作时，只需调整指针指向即可，无需移动后续数据，从而保证了修改操作的高效率；然而，其查找效率较低，这也是链表与数组的主要区别所在。链表的存储结构示意图如下：
解决单链表反转问题，至少存在以下三种可行的实现路径：
1. 先对原链表执行头部删除操作，随后对新链表执行头部插入操作； 2. 利用三个指针进行辅助：p0指向当前节点的前一个节点，p1指向当前正在处理的节点，p2指向当前节点的下一个节点； 3. 采用递归方式实现反转逻辑。
2. 方式一的具体实现：
1) 初始化创建一个空的新链表；
2）从旧链表中依次取出头结点的元素，将该元素的next指针指向新链表的当前头指针，同时将旧链表的头结点指针移动至下一个元素；
3）重复执行第2）步的操作，直至旧链表中的所有节点均被处理完毕；
4）最终形成的新链表即为反转后的结果，具体结构如下：
5）对应的Python代码实现如下：
# encoding=utf-8
import copy
class Node:
"""节点类，包含值和下一个节点的指针"""
def __init__(self, value, next=None):
self.value = value
self.next = next
def __str__(self):
return "Node value:%s" % self.value
class LinkedList:
def __init__(self, head=None, tail=None):
self.head = head
self.tail = tail
def get_all(self):
"""获取链表中所有的节点"""
nodes = []
temp = self.head
while temp:
nodes.append(temp.value)
temp = temp.next
return nodes
def add_node(self, value):
"""在列表中添加节点"""
node = Node(value)
# 空链表,收尾指针都指向新增加的节点
if self.head is None:
self.head = node
self.tail = node
else:
self.tail.next = node
self.tail = node
def reverse_list(self):
"""反转单向列表
思路一：先对原链表做头删操作，再对新链表做头插
"""
# 定义一个新的链表
new_list_node = LinkedList()
temp = copy.deepcopy(self.head)
while temp:
# 1.对之前的链表做头删除操作
node = temp
temp = temp.next
# 2.对新的链表做头插入操作
if new_list_node.head is None:
new_list_node.tail = node
node.next = new_list_node.head
new_list_node.head = node
return new_list_node
if __name__ == "__main__":
l = LinkedList()
for i in range(5):
l.add_node(i)
new_list_node = l.reverse_list()
print(new_list_node.get_all())
print(new_list_node.tail)3. 方式二：三指针迭代法
该方法借助三个指针完成反转：p0指向已反转部分的最后一个节点（即前一个节点），p1指向当前正在处理的节点，p2指向下一个待处理节点。具体操作流程为：将p1的next指针指向p0，随后将p0移动至p1的位置，p1移动至p2的位置；若p1不为空，则重复上述步骤。最终，p0将指向新链表的头节点。
1）初始状态时p0为空；将p1指向原链表的头节点，将p1的next指针指向p0（即None），并将p2指向原链表的下一个节点：
2）调整三个指针的指向关系：将p0更新为p1，将p1更新为p2，并将p1的next指向p0；随后将p2移动至其下一个节点：
3）循环执行上述步骤，直到p1指向的节点为空。最终得到的链表结构如下：
4）对应的Python代码实现如下：
# encoding=utf-8
import copy
class Node:
"""节点类，包含值和下一个节点的指针"""
def __init__(self, value, next=None):
self.value = value
self.next = next
def __str__(self):
return "Node value:%s" % self.value
class LinkedList:
def __init__(self, head=None, tail=None):
self.head = head
self.tail = tail
def get_all(self):
"""获取链表中所有的节点"""
nodes = []
temp = self.head
while temp:
nodes.append(temp.value)
temp = temp.next
return nodes
def add_node(self, value):
"""在列表中添加节点"""
node = Node(value)
# 空链表,收尾指针都指向新增加的节点
if self.head is None:
self.head = node
self.tail = node
else:
self.tail.next = node
self.tail = node
def reverse_list(self):
"""
反转单向列表
思路二：通过3个指针实现，p0指向前一个节点的指针，p1表示当前节点的指针，p2表示下一个节点的指针
:return: LinkedList 对象
"""
p1 = copy.deepcopy(self.head)
p2 = p1.next
# 定义一个新的链表对象
new_list_node = LinkedList()
while p1:
if new_list_node.head is None:
new_list_node.tail = p1
# 将p1的next指向新链表的头结点
p1.next = new_list_node.head
# 将新链表的头结点指向p1
new_list_node.head = p1
# 将p1指向p2
p1 = p2
# 判断p2是否指向了链表的末尾
if p2:
p2 = p2.next
return new_list_node
if __name__ == "__main__":
l = LinkedList()
for i in range(5):
l.add_node(i)
new_list_node = l.reverse_list()
print(new_list_node.get_all())
print(new_list_node.tail)4. 方式三：递归法
递归的核心思想是将复杂问题分解为结构一致的子问题，但必须设定明确的终止条件。单链表反转同样适用递归思路：若传入的节点不是最后一个节点，则将该节点的下一个节点作为参数递归调用；当传入的是最后一个节点时，开始逐级返回结果。
1）将链表中的每个节点依次作为参数传入reverse_list函数中；
2）当递归到达最后一个节点时，以该节点为头节点构建新链表，并将其返回；
3）上一层调用者接收返回的链表后，将当前传入的节点追加到该链表的尾部；
4）逐级向上返回，直至回到最初的reverse_list函数调用，最终生成并返回完整的新链表。
5）对应的Python代码实现如下：
# encoding=utf-8
import copy
class Node:
"""节点类，包含值和下一个节点的指针"""
def __init__(self, value, next=None):
self.value = value
self.next = next
def __str__(self):
return "Node value:%s" % self.value
class LinkedList:
def __init__(self, head=None, tail=None):
self.head = head
self.tail = tail
def get_all(self):
"""获取链表中所有的节点"""
nodes = []
temp = self.head
while temp:
nodes.append(temp.value)
temp = temp.next
return nodes
def add_node(self, value):
"""在列表中添加节点"""
node = Node(value)
# 空链表,收尾指针都指向新增加的节点
if self.head is None:
self.head = node
self.tail = node
else:
self.tail.next = node
self.tail = node
def reverse_list(self, node):
"""
反转单链表
思路三：用递归实现
:return:LinkedList 对象
"""
if node.next is None:
return LinkedList(node, node)
temp = copy.deepcopy(node)
# 断开当前节点的连接
temp.next = None
# 将当前节点放到内层递归返回的链表结尾
l = self.reverse_list(node.next)
l.tail.next = temp
l.tail = temp
return l
if __name__ == "__main__":
l = LinkedList()
for i in range(5):
l.add_node(i)
new_list_node = l.reverse_list1()
print(new_list_node.get_all())
print(new_list_node.tail)以上即为本文关于单链表反转算法的全部内容，希望能为读者的学习提供有益帮助，也欢迎大家继续支持本站。
免责声明：本文内容仅供参考，不代表本站观点。转载或引用请注明出处。
