如何使用Python函数来实现链表的反转操作?
发布时间:2023-07-03 19:15:17
链表反转是指将链表的指针方向逆转,使链表的最后一个节点成为新的头节点。下面是使用Python函数实现链表反转的方法:
1. 定义一个Node类,表示链表的节点。该类包含一个值属性和一个指针属性,指向下一个节点。
class Node:
def __init__(self, value):
self.value = value
self.next = None
2. 定义一个reverse_linked_list函数,接收一个链表的头节点作为参数。该函数通过迭代方式实现链表反转。
def reverse_linked_list(head):
prev = None
curr = head
while curr:
next = curr.next
curr.next = prev
prev = curr
curr = next
return prev
3. 在主函数中创建一个链表,并调用reverse_linked_list函数进行链表反转。
def main():
# 创建链表
head = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
head.next = node2
node2.next = node3
node3.next = node4
# 输出原始链表
print("原始链表:")
curr = head
while curr:
print(curr.value, end=" ")
curr = curr.next
print()
# 调用函数进行链表反转
new_head = reverse_linked_list(head)
# 输出反转后的链表
print("反转后的链表:")
curr = new_head
while curr:
print(curr.value, end=" ")
curr = curr.next
print()
if __name__ == "__main__":
main()
以上代码的输出结果为:
原始链表: 1 2 3 4 反转后的链表: 4 3 2 1
通过以上代码,我们可以看到,使用Python函数实现链表反转操作的关键是通过迭代的方式,依次将每个节点的指针指向前一个节点。反转完成后,原链表的头节点变为尾节点,而原链表的尾节点变为新链表的头节点。
