python如何实现单向链表及单向链表的反转

下面我将详细讲解如何使用Python实现单向链表及单向链表的反转。

单向链表

单向链表是一种常见的线性数据结构，它由一个个节点组成，每个节点包含一个数据元素和一个指向后继节点的指针。单向链表的头节点通常不包含任何数据信息，只是一个辅助节点，指向第一个真正包含数据信息的节点。

实现方法

我们可以使用Python中的类来实现单向链表。类中定义一个Node类表示每个节点，每个节点包含一个数据元素和一个指向后继节点的指针。在类中定义链表的一些基本操作，如插入、删除和搜索等。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = Node(None)

    # 插入
    def insert(self, data):
        new_node = Node(data)
        current_node = self.head
        while current_node.next:
            current_node = current_node.next
        current_node.next = new_node

    # 删除
    def delete(self, data):
        current_node = self.head
        while current_node.next:
            if current_node.next.data == data:
                current_node.next = current_node.next.next
                return
            current_node = current_node.next
        print("Not found!")

    # 搜索
    def search(self, data):
        current_node = self.head
        while current_node.next:
            current_node = current_node.next
            if current_node.data == data:
                return current_node
        return None

    # 输出链表
    def __str__(self):
        current_node = self.head
        res = ''
        while current_node.next:
            current_node = current_node.next
            res += str(current_node.data) + ' -> '
        return res + 'None'

示例说明

我们可以通过以下代码来测试我们实现的单向链表：

linked_list = LinkedList()
linked_list.insert(1)
linked_list.insert(2)
linked_list.insert(3)
linked_list.insert(4)

print(linked_list)  # 输出 1 -> 2 -> 3 -> 4 -> None

linked_list.delete(3)

print(linked_list)  # 输出 1 -> 2 -> 4 -> None

node = linked_list.search(2)

print(node.data)  # 输出 2

单向链表的反转

单向链表的反转是指将单向链表中的所有节点顺序颠倒过来，使得原本的尾节点变成新的链表头节点。单向链表的反转可以使用迭代或递归来实现。

实现方法

迭代法

我们可以通过循环遍历链表，每次将当前节点的指针指向前一个节点来实现链表的反转。需要注意的是，在反转链表的过程中，必须记录下前一个节点和当前节点。

class LinkedList:
    # ...

    # 链表反转
    def reverse(self):
        current_node = self.head.next
        prev_node = None
        while current_node:
            next_node = current_node.next
            current_node.next = prev_node
            prev_node = current_node
            current_node = next_node
        self.head.next = prev_node

递归法

递归法是将链表反转问题转化为该链表第二个节点开始往后的节点序列的反转问题，利用递归实现链表反转。

class LinkedList:
    # ...

    # 链表反转
    def reverse_recursive(self, node):
        if not node or not node.next:
            return node
        new_head = self.reverse_recursive(node.next)
        node.next.next = node
        node.next = None
        return new_head

示例说明

我们可以通过以下代码来测试我们实现的单向链表的反转：

linked_list = LinkedList()
linked_list.insert(1)
linked_list.insert(2)
linked_list.insert(3)

linked_list.reverse()

print(linked_list)  # 输出 3 -> 2 -> 1 -> None

linked_list_reverse = LinkedList()
linked_list_reverse.insert(1)
linked_list_reverse.insert(2)
linked_list_reverse.insert(3)

new_head = linked_list_reverse.reverse_recursive(linked_list_reverse.head.next)

linked_list_reverse.head.next = new_head

print(linked_list_reverse)  # 输出 3 -> 2 -> 1 -> None

以上就是实现单向链表及单向链表反转的完整攻略，希望能对你有所帮助。