什么是ListNode？它在数据结构中扮演什么角色？

链表节点（ListNode）简介

链表是一种常见的数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针，在Python中，可以使用类来定义链表节点，并实现基本的链表操作，本文将详细介绍链表节点的定义、常见操作以及相关示例代码。

ListNode类的定义

我们定义一个ListNode类，它包含两个属性：val用于存储节点的值，next用于指向下一个节点。

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

创建链表

可以通过实例化多个ListNode对象并将它们链接起来创建链表。

创建三个节点
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
将节点链接起来形成链表
node1.next = node2
node2.next = node3

这样，node1就是链表的头节点，整个链表如下所示：

1 > 2 > 3

遍历链表

遍历链表时，可以从头节点开始，依次访问每个节点直到末尾（即next为None）。

def print_list(head):
    current = head
    while current:
        print(current.val, end=" > ")
        current = current.next
    print("None")
调用函数打印链表
print_list(node1)

输出结果为：

1 > 2 > 3 > None

插入节点

在链表中插入节点可以有几种情况：在头部插入、在中间插入以及在尾部插入，这里以在尾部插入为例：

def insert_at_tail(head, val):
    new_node = ListNode(val)
    if not head:
        return new_node
    current = head
    while current.next:
        current = current.next
    current.next = new_node
    return head
在尾部插入值为4的新节点
insert_at_tail(node1, 4)
print_list(node1)

输出结果为：

1 > 2 > 3 > 4 > None

删除节点

删除节点时需要找到要删除节点的前一个节点，并将其next指向要删除节点的下一个节点，以下示例删除值为3的节点：

def delete_node(head, val):
    if not head:
        return None
    if head.val == val:
        return head.next
    current = head
    while current.next and current.next.val != val:
        current = current.next
    if current.next:
        current.next = current.next.next
    return head
删除值为3的节点
delete_node(node1, 3)
print_list(node1)

输出结果为：

1 > 2 > 4 > None

查找节点

查找节点可以通过遍历链表实现，找到第一个值等于目标值的节点并返回其引用，如果未找到，则返回None。

def find_node(head, val):
    current = head
    while current:
        if current.val == val:
            return current
        current = current.next
    return None
查找值为2的节点
result = find_node(node1, 2)
if result:
    print(f"Found node with value: {result.val}")
else:
    print("Node not found")

输出结果为：

Found node with value: 2

反转链表

反转链表需要逐个调整每个节点的next指针，使其指向前一个节点，以下是反转链表的实现：

def reverse_list(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev
反转链表
reversed_head = reverse_list(node1)
print_list(reversed_head)

输出结果为：

4 > 2 > 1 > None

操作	描述	示例代码
创建链表	初始化多个节点并链接成链表	node1 = ListNode(1); node2 = ListNode(2); node1.next = node2
遍历链表	从头节点开始依次访问每个节点	while current: ...
插入节点	在指定位置插入新节点	new_node.next = node2
删除节点	删除指定值的节点	if current.val == val: ...
查找节点	查找第一个值等于目标值的节点	while current: ...
反转链表	将链表中的节点顺序颠倒	prev, current = None, ...

FAQs

Q1: 如何在链表中插入一个新节点？

A1: 在链表中插入新节点可以根据插入位置不同分为几种情况，以在尾部插入为例，首先创建一个新节点，然后遍历到链表的最后一个节点，将其next指向新节点即可，具体实现可以参考上面的insert_at_tail函数。

Q2: 如何删除链表中的某个节点？

A2: 删除链表中的某个节点需要找到该节点的前一个节点，并将其next指向要删除节点的下一个节点，具体实现可以参考上面的delete_node函数，需要注意的是，如果要删除的是头节点，则需要更新头指针。