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

推荐答案

// www.javascriptcn.com code example
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insert(self, data, position):
        new_node = Node(data)
        if position == 0:
            new_node.next = self.head
            self.head = new_node
        else:
            current = self.head
            for _ in range(position - 1):
                if current is None:
                    raise IndexError("Position out of bounds")
                current = current.next
            new_node.next = current.next
            current.next = new_node

    def print_list(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# 示例用法
ll = LinkedList()
ll.insert(10, 0)  # 在位置0插入10
ll.insert(20, 1)  # 在位置1插入20
ll.insert(30, 1)  # 在位置1插入30
ll.print_list()  # 输出: 10 -> 30 -> 20 -> None

本题详细解读

链表节点的定义

链表是由节点组成的，每个节点包含两个部分：

• data: 存储节点的数据。
• next: 指向下一个节点的指针。

在Python中，我们可以通过定义一个Node类来表示链表中的节点。

链表的定义

链表本身可以通过一个LinkedList类来表示，该类包含一个指向链表头节点的指针head。

插入节点的步骤

1. 创建新节点：首先，创建一个新的Node对象，并将要插入的数据存储在其中。
2. 处理插入位置为0的情况：如果要插入的位置是0（即在链表头部插入），则将新节点的next指针指向当前的头节点，然后将链表的head指针指向新节点。
3. 处理其他位置的情况：如果要插入的位置不是0，则需要遍历链表，找到插入位置的前一个节点。然后将新节点的next指针指向当前节点的下一个节点，再将当前节点的next指针指向新节点。
4. 边界检查：在遍历链表时，如果发现当前节点为None，说明插入位置超出了链表的范围，应该抛出异常。

示例解释

在示例中，我们首先在位置0插入10，链表变为10 -> None。然后在位置1插入20，链表变为10 -> 20 -> None。最后在位置1插入30，链表变为10 -> 30 -> 20 -> None。

时间复杂度

• 插入到头部：时间复杂度为O(1)，因为只需要修改头指针。
• 插入到其他位置：时间复杂度为O(n)，其中n是链表的长度，因为需要遍历链表找到插入位置。

空间复杂度

• 空间复杂度为O(1)，因为只需要常数级别的额外空间来存储新节点。