接下来我将详细讲解如何使用Python的递归和迭代方法实现链表的反转。
什么是链表反转
链表反转(reverse a linked list)指的是将链表中的所有节点的指针方向都倒转,即原来指向下一个节点的指针变为指向前一个节点,这样可以让链表的尾部变为头部,实现链表的逆序。
实现方法
链表反转可以使用递归和迭代两种方法进行实现。
递归方法
递归反转链表的思路是:
- 递归到链表的最后一个节点;
- 从最后一个节点开始,将每个节点的下一个节点的指针指向自己;
- 返回反转后的链表头节点。
用Python代码实现递归反转链表:
# 定义节点结构
class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 递归反转链表
def reverseList(head):
if not head or not head.next:
return head
newHead = reverseList(head.next)
head.next.next = head
head.next = None
return newHead
使用以下代码进行测试:
# 构造链表
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
# 打印反转前的链表
p = node1
while p:
print(p.val, end=" ")
p = p.next
print()
# 反转链表
newHead = reverseList(node1)
# 打印反转后的链表
p = newHead
while p:
print(p.val, end=" ")
p = p.next
print()
输出结果如下:
1 2 3 4 5
5 4 3 2 1
迭代方法
迭代反转链表的思路是:
- 使用三个指针分别指向当前节点、前一个节点和后一个节点;
- 当前节点指向前一个节点,然后三个指针依次向后移动一个节点;
- 返回反转后的链表头节点。
用Python代码实现迭代反转链表:
# 迭代反转链表
def reverseList(head):
if not head or not head.next:
return head
pre = None
cur = head
nxt = head.next
while cur:
cur.next = pre
pre = cur
cur = nxt
nxt = nxt.next if nxt else None
return pre
使用以下代码进行测试:
# 构造链表
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
# 打印反转前的链表
p = node1
while p:
print(p.val, end=" ")
p = p.next
print()
# 反转链表
newHead = reverseList(node1)
# 打印反转后的链表
p = newHead
while p:
print(p.val, end=" ")
p = p.next
print()
输出结果如下:
1 2 3 4 5
5 4 3 2 1
总结
递归和迭代是两种常见的解决链表反转问题的方法。对于链表较长的情况下,使用迭代方法需要额外的空间来保存三个指针,因此递归方法更节省空间。但是在Python中,递归深度有限制,因此对于较长的链表还是推荐使用迭代方法来实现反转。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:python递归&迭代方法实现链表反转 - Python技术站