单链表找公共结点时间复杂度

单链表找公共结点的时间复杂度是O(m + n)，其中m和n分别是两个链表的长度。

要找到两个单链表的公共结点，可以先分别遍历两个链表，得到它们的长度。然后让较长的链表先移动差值个结点，使得两个链表剩余的长度相等。接下来同时遍历两个链表，比较每个结点是否相同，直到找到第一个相同的结点或者遍历到链表的末尾。

由于需要遍历两个链表，所以时间复杂度为O(m + n)。

相关问题

二叉排序树插入结点时间复杂度

### 二叉排序树插入结点的时间复杂度分析

对于二叉排序树（BST），插入操作涉及找到合适的位置并放置新节点。此过程类似于查找操作，因为需要遍历从根到某个叶子路径上的各个节点。

当二叉排序树保持平衡状态时，树的高度大约为 \(\log_2 n\) ，其中 \(n\) 是节点数量。在这种情况下，插入一个新节点所需的最大比较次数等于树的高度，即时间复杂度为 O(log₂n)[^2]。

然而，在最坏的情况下——例如连续插入已按升序或降序排列的数据序列——这将导致生成的二叉排序树变成线性的链表形式，此时高度变为\(n\) 。因此，在这种极端情形下，插入操作的时间复杂度会恶化至O(n)。

通常来说，实际应用中的二叉排序树可能既不是完全平衡也不是极度倾斜的状态；所以平均情况下的时间复杂度介于上述两种极限之间。为了维持良好的性能表现，实践中常采用自平衡策略来构建AVL树、红黑树等形式更为稳定的变种版本。

def insert_into_bst(root, value):
    if root is None:
        return TreeNode(value)

    current = root
    while True:
        if value < current.val:
            if not current.left:
                current.left = TreeNode(value)
                break
            else:
                current = current.left
        elif value > current.val:
            if not current.right:
                current.right = TreeNode(value)
                break
            else:
                current = current.right
    
    # Rebalance tree here (if implementing a self-balancing BST like AVL or Red-Black Tree)
    
    return root

平衡二叉树删除结点时间复杂度

### 平衡二叉树中删除节点的时间复杂度

对于平衡二叉树中的删除操作，最坏情况下的时间复杂度取决于树的高度 \(h\)。在最坏情况下，可能需要从根节点遍历到最深的叶节点[^1]。

#### 删除操作的具体过程
当执行删除操作时，通常会遇到三种情形：

- 被删节点无子节点：直接移除该节点。
- 被删节点有一个子节点：用其唯一的子节点替代它。
- 被删节点有两个子节点：找到右子树中最左端的节点（即最小值），替换被删节点的位置并继续处理新位置上的删除问题。

每种情形下都需要更新路径上各节点的信息来保持树结构的自平衡特性，这增加了额外的操作开销但不会显著影响整体渐近时间复杂度。

#### 特殊类型的平衡二叉树

不同种类的自平衡二叉查找树有不同的机制维持自身的高度接近于 \(\log_2{n}\)，从而保证了高效的查询性能以及相对稳定的插入和删除效率。例如AVL树严格控制左右两侧高度差不超过1；红黑树则通过染色规则间接实现相似效果[^2]。

因此，在理想状态下，这些经过优化设计的数据结构能够确保删除操作平均与最好情况均达到对数级别的时间消耗\(O(\log n)\)而非线性的\(O(n)\)。

def delete_node(root, key):
    if not root:
        return root
    
    # 标准BST删除逻辑...
    
    # 更新当前节点的高度
    root.height = 1 + max(get_height(root.left), get_height(root.right))
  
    balance_factor = get_balance_factor(root)

    # 执行旋转以恢复平衡...

    return root