链表在计算机科学中是一种非常重要的数据结构。它由节点组成,每个节点都包含数据和指向下一个节点的指针。在Python中,我们可以使用类来实现链表数据结构。而链表的反转是链表操作中的一个基本问题,在本文中,我们将介绍Python中如何反转链表。
class Node: def __init__(self, val=None): self.val = val self.next = None class LinkedList: def __init__(self): self.head = None def add_node(self, val): if not self.head: self.head = Node(val) else: temp_node = self.head while temp_node.next: temp_node = temp_node.next temp_node.next = Node(val) def print_list(self): curr_node = self.head while curr_node: print(curr_node.val) curr_node = curr_node.next def reverse_list(self): prev_node = None curr_node = self.head while curr_node: next_node = curr_node.next curr_node.next = prev_node prev_node = curr_node curr_node = next_node self.head = prev_node linked_list = LinkedList() linked_list.add_node(1) linked_list.add_node(2) linked_list.add_node(3) linked_list.add_node(4) linked_list.print_list() linked_list.reverse_list() linked_list.print_list()
上述代码实现了一个简单的单向链表,包括添加节点、打印链表和反转链表三个操作。其中反转链表的实现方法为:
- 设前驱节点初始值为None,当前节点为链表头结点
- 遍历整个链表,将当前节点的next指针指向前驱节点
- 将当前节点设为前驱节点,将下一个节点设为当前节点,继续遍历
- 当遍历完链表后,将链表头结点设为前驱节点
在运行完反转操作后,再次打印链表即可看到反转后的结果。
在Python中,反转链表是一个非常基本的操作,可以帮助我们更好地理解链表的结构和操作。同时,对于面试题和编程挑战,也是必不可少的技能。