Блог

извините за вопрос новичка здесь.

Я пытаюсь реализовать метод вставки для класса связанного списка, используя рекурсию, как показано в приведенном ниже коде.
Однако, когда я пытаюсь это сделать, я получаю список, который бесконечно повторяет значение, которое я хочу вставить.

напр.
1-й узел — «а»,
2-й узел — «в»,
3-й узел — «с».

Если бы я использовал код для вставки «d» в качестве нового 3-го узла, я бы получил » abddddddd….» до бесконечности.

Был бы очень признателен за некоторые советы о том, что вызвало такое поведение.

 class linked_list():


    def __init__(self, node):
        self.node = node


    def insert_at_index (self, index, value, node=None, current_index=0):
        def insert_recur(index, new_node, node, current_index):
            if current_index == index:
                node.next_node = new_node
                new_node.next_node = node.next_node
                return None
            else:
                return insert_recur(index, new_node, node.next_node, current_index 1)
        
        new_node = Node(value)
        if index == 0:
            new_node.next_node = self.node
            self.node = new_node
            return
        else:
            node = self.node 
            insert_recur(index, new_node, node, current_index)
 

Проблема в том, что здесь:

 if current_index == index:
    node.next_node = new_node
    new_node.next_node = node.next_node
    return None
 

После присвоения node.next_node = new_node старое значение node.next_node было потеряно. Последующее задание, new_node.next_node = node.next_node , эквивалентно new_node.next_node = new_node . Так new_node становится его собственным преемником.

Попробуйте изменить порядок выполнения заданий:

 if current_index == index:
    new_node.next_node = node.next_node
    node.next_node = new_node
    return None