在有序链表中插入元素

在上一篇文章中，我们介绍了如何删除链表中首次出现的指定关键字。在这篇文章中，让我们一起来探讨如何在有序链表中插入一个新的节点，使得链表在插入操作后依然保持有序。

我们可以假设链表是按升序排列的。

示例

输入： 链表：

25 -> 36 -> 47 -> 58 -> 69 -> 80
数据为 45 的新节点

输出：

25 -> 36 -> 47 -> 45 -> 58 -> 69 -> 80

解释： 新节点包含数据 45。我们需要将 45 插入到 36 和 47 之间。

算法

为了在有序链表中插入节点，我们需要遵循以下步骤：

• 创建新节点：首先，我们为要插入的数据创建一个新节点（比如 new_node）。
• 检查头部插入：如果链表为空（INLINECODE7b007df5 为 null），或者新节点的数据小于头节点的数据，我们将新节点设为新的头节点，并将其 INLINECODEda062285 指向原来的头节点。
• 寻找插入位置：如果不需要插入在头部，我们需要遍历链表，寻找合适的插入位置。

* 我们使用一个临时节点（INLINECODE2117428d）从 INLINECODE42cba27d 开始遍历。

* 只要 INLINECODEc38e3f83 不为 null 且 INLINECODEefc5b791 小于 INLINECODE50e4484a，我们就继续后移 INLINECODEb28a2ced 指针。

* 这个循环结束后，INLINECODE098cbdeb 将指向新节点前驱节点（即新节点应该插在 INLINECODE1312c963 和 current.next 之间）。

• 插入节点：最后，我们将新节点链接到链表中。

* 将 INLINECODE988b31a9 指向 INLINECODE7acb284d。

* 将 INLINECODE449f6ba6 指向 INLINECODEc5b30635。

代码实现

以下是上述算法的代码实现：

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

def sortedInsert(head, new_node):
    # 1. 如果链表为空，或者新节点应该成为新的头节点
    if head is None or head.data >= new_node.data:
        new_node.next = head
        head = new_node
        return head

    # 2. 寻找新节点应该插入的前驱节点
    current = head
    while current.next is not None and current.next.data  36 -> 47 -> 58 -> 69 -> 80
    head = newNode(25)
    head.next = newNode(36)
    head.next.next = newNode(47)
    head.next.next.next = newNode(58)
    head.next.next.next.next = newNode(69)
    head.next.next.next.next.next = newNode(80)

    print("原始链表:")
    printList(head)

    # 插入包含数据 45 的新节点
    new_node = newNode(45)
    head = sortedInsert(head, new_node)

    print("插入 45 后的链表:")
    printList(head)

复杂度分析

• 时间复杂度：O(N)

* 在最坏的情况下（例如，我们要插入的节点值大于链表中的所有节点，或者插入在链表末尾），我们需要遍历整个链表。因此，时间复杂度是线性的，与链表的长度 N 成正比。

• 空间复杂度：O(1)

* 我们只使用了一个固定的额外指针空间（如 current），不随输入规模 N 变化，因此空间复杂度是常数级的。

总结

在这篇文章中，我们学习了如何在有序链表中插入一个新节点。这个过程的核心在于遍历链表，找到最后一个比新节点小的节点，也就是新节点的前驱节点。将新节点插入到这个前驱节点之后，就能保证链表的有序性。