如何在链表中查找一个节点？

推荐答案

-- -------------------- ---- -------
----- -----
    --- -------------- ------
        --------- - ----
        --------- - ----

--- --------------- --------
    ------- - ----
    ----- ------- -- --- -----
        -- ------------ -- -------
            ------ -------
        ------- - ------------
    ------ ----

本题详细解读

链表节点的定义

在链表中，每个节点通常包含两个部分：

• data：存储节点的值。
• next：指向下一个节点的指针。

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

查找节点的过程

1. 初始化：从链表的头节点 head 开始。
2. 遍历链表：使用一个指针 current 来遍历链表，从头节点开始，依次检查每个节点的 data 是否等于目标值 target。
3. 找到目标节点：如果找到 current.data == target，则返回当前节点 current。
4. 未找到目标节点：如果遍历完整个链表仍未找到目标节点，则返回 None。

def find_node(head, target):
    current = head
    while current is not None:
        if current.data == target:
            return current
        current = current.next
    return None

时间复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。最坏情况下需要遍历整个链表。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

示例

假设链表为 1 -> 2 -> 3 -> 4，查找值为 3 的节点：

head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)

result = find_node(head, 3)
print(result.data)  # 输出: 3

在这个例子中，find_node 函数会返回值为 3 的节点。