代码收藏家技术教程 2024-08-28

Python中ListNode链表的深度解析

在Python里我们常用ListNode 类是作为实现链表（Linked List）的基础单元。链表是一种常见的数据结构，其中每个节点（node）包含一个数据元素和一个指向下一个节点的引用（或指针）。下面我们详细解释一下 ListNode 类的原理和用法。

可能比较抽象，但也没必要硬理解，知道有这么个玩意就行

具象出来的东西就是类似：1->2->3->4 这样的就是链表

1. ListNode 类的定义

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

构成部分

初始化方法 __init__：

__init__ 是类的构造方法，当我们创建一个新的 ListNode 实例时，这个方法会自动调用。

它有两个参数：

val：存储在这个节点中的数据，默认值为 0。

next：指向下一个节点的引用，默认值为 None。

这两个参数会被赋值给实例的属性 self.val 和 self.next。

具体解释

val：

这是一个整数，表示当前节点存储的值。每个节点只存储一个整数值。

这是一个指针或引用，指向链表中的下一个节点。如果没有下一个节点（例如这是链表的最后一个节点），则 next 的值为 None。

2. 示例用法

（1）创建单个节点

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

node = ListNode(5)
print(node.val)  # 输出: 5
print(node.next) # 输出: None

在这个例子中，我们创建了一个值为 5 的节点，它没有下一个节点，所以 next 为 None。

（2）创建一个简单的链表

我们可以通过链接多个 ListNode 实例来创建一个链表。比如，创建一个包含三个节点的链表：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 创建节点
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)

# 链接节点
node1.next = node2
node2.next = node3

这个链表为：1 -> 2 -> 3 -> None

（3）遍历链表

我们可以遍历这个链表并打印每个节点的值：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 创建节点
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)

# 链接节点
node1.next = node2
node2.next = node3

current = node1
while current:
    print(current.val)
    current = current.next

（4）使用辅助函数创建和打印链表

# 定义单链表的节点类
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val  # 节点的值
        self.next = next  # 指向下一个节点的指针

# 辅助函数：创建链表
def create_linked_list(lst):
    dummy = ListNode()  # 创建一个虚拟头节点
    current = dummy  # 设置当前节点为虚拟头节点
    for number in lst:  # 遍历输入的列表
        current.next = ListNode(number)  # 创建新节点，连接到当前节点的后面
        current = current.next  # 将当前节点指针移动到下一个节点
    return dummy.next  # 返回虚拟头节点的下一个节点，即实际的链表头

# 辅助函数：打印链表
def print_linked_list(node):
    while node is not None:  # 遍历链表直到链表末尾
        # 打印节点的值，如果存在下一个节点则打印箭头，否则换行
        print(node.val, end=" -> " if node.next else "\n")
        node = node.next  # 移动到下一个节点

# 示例输入
l1 = create_linked_list([2, 4, 3])  # 构建链表 l1 = [2, 4, 3]

# 打印结果链表
print_linked_list(l1)  # 结果应该是 2 -> 4 -> 3