python单向链表实例详解

下面是关于“Python单向链表实例详解”的完整攻略：

什么是单向链表？

单向链表（Singly Linked List）是一种常见的数据结构，它由多个节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。相比于数组，单向链表具有动态操作、空间灵活等优势，在实际应用中也很常见。

如何实现单向链表？

在 Python 中，我们可以用类来定义一个单向链表，每个节点用一个类实例来表示。以下是一个最简单的示例：

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

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

在这里，我们定义了一个 Node 类，包含数据域 data 和指针域 next；同时，我们定义了一个 LinkedList 类，初始时链表为空，头结点指针为空。

单向链表的基本操作

1. 添加元素

向链表中添加元素时，我们需要创建一个新的节点，然后将它插入到链表的末尾。以下是一个示例：

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

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

在这里，我们定义了一个 append 方法，用于将新元素添加到链表末尾。首先，我们创建一个新的节点 new_node，其数据域为 data；然后，我们检查链表是否为空，如果是，则将 new_node 设置为头结点；否则，用 last_node 变量指向链表的最后一个节点，然后将 new_node 插入到链表的末尾。

2. 遍历链表

遍历链表时，我们只需要从头节点开始依次访问每个节点即可。以下是一个示例：

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

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def traverse(self):
        if self.head is None:
            print("List is empty")
            return
        current_node = self.head
        while current_node:
            print(current_node.data, end=" ")
            current_node = current_node.next

在这里，我们定义了一个 traverse 方法，用于遍历链表并输出每个节点的数据域。首先，我们检查链表是否为空，如果是，则输出 “List is empty” ；否则，我们用 current_node 变量指向链表的头结点，然后依次访问每个节点并输出其数据域。

以下是一个示例输出：

linked_list = LinkedList()
linked_list.append("A")
linked_list.append("B")
linked_list.append("C")

linked_list.traverse()
# Output: A B C

可以看到，我们成功地创建并遍历了一个包含 3 个元素的链表。

示例应用

1. 单向链表中的常见问题：查找中间节点

对于链表中除了头尾节点以外的其他节点，我们可以用以下方法来查找其中间节点：

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

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def find_middle_node(self):
        if self.head is None:
            return None
        slow_pointer = self.head
        fast_pointer = self.head
        while fast_pointer and fast_pointer.next:
            slow_pointer = slow_pointer.next
            fast_pointer = fast_pointer.next.next
        return slow_pointer

在这里，我们定义了一个 find_middle_node 方法，用于查找链表的中间节点。首先，我们检查链表是否为空，如果是，则返回 None；否则，我们用 slow_pointer 和 fast_pointer 两个指针分别指向头结点，并进行以下操作：

• 正常情况下，fast_pointer 走两步，slow_pointer 走一步，直到 fast_pointer 无法再走两步为止；
• 最后，slow_pointer 指向的节点即为中间节点。

以下是一个示例输出：

linked_list = LinkedList()
linked_list.append("A")
linked_list.append("B")
linked_list.append("C")
linked_list.append("D")
linked_list.append("E")
linked_list.append("F")

middle_node = linked_list.find_middle_node()
print(middle_node.data)
# Output: D

2. 单向链表的反转

对于一个链表，我们可以用以下方法来反转它：

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

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def reverse(self):
        previous_node = None
        current_node = self.head
        while current_node:
            next_node = current_node.next
            current_node.next = previous_node
            previous_node = current_node
            current_node = next_node
        self.head = previous_node

在这里，我们定义了一个 reverse 方法，用于反转链表。首先，我们用 previous_node 变量指向 None，用 current_node 变量指向链表的头结点；然后，依次处理每个节点：

• 将 current_node 的 next 指针指向 previous_node；
• 将 previous_node 指向 current_node；
• 将 current_node 指向 next_node。

最后，将 self.head 指向反转后的链表的第一个节点。

以下是一个示例输出：

linked_list = LinkedList()
linked_list.append("A")
linked_list.append("B")
linked_list.append("C")
linked_list.append("D")
linked_list.append("E")
linked_list.append("F")

print("Original list:")
linked_list.traverse()
# Output: A B C D E F

linked_list.reverse()

print("Reversed list:")
linked_list.traverse()
# Output: F E D C B A

可以看到，我们成功地反转了一个链表。

阅读剩余 77%