"""
Что происходит в коде этой функции?
На вход она принимает голову списка, индекс (по которому мы добавляем элемент) и значение нового элемента. Возвращать функция будет голову списка — то есть ту записку, которую мы вручим Рите в начале приключения.
Для того чтобы найти элемент, за которым вставим новый, необходимо найти элемент на позиции index-1. Назовём его previous_node (англ. previous, «предыдущий»). А дальше вставляем его в середину списка так, как мы только что это разобрали. Посмотрите ещё раз на схему вставки элемента в список:
у нового элемента ставим в next тот элемент, на который указывал previous_node.next;
previous_node.next перенаправляем так, чтобы он указывал на добавляемый элемент.
Обратите внимание, мы отдельно обрабатываем случай, когда хотим вставить элемент в голову списка, так как на неё не указывает никакой элемент. Но при этом программная реализация не требует специально разбирать вставку на последнее место в связном списке. Так происходит потому, что вставка в конец — это на самом деле вставка между вершиной со значением и вершиной с None-объектом. До вставки последняя вершина указывала на None. После вставки вершина, которая раньше указывала на None, теперь ссылается на новую. А новая ссылается на None.
После того как мы поменяли ссылки, вернём голову списка из функции.
"""


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


def get_node_by_index(node, index):
    while index:
        node = node.next
        index -= 1
    return node


def insert_node(head, index, value):
    new_node = Node(value)
    if index == 0:
        new_node.next = head
        return new_node
    previous_node = get_node_by_index(head, index - 1)
    new_node.next = previous_node.next
    previous_node.next = new_node
    return head


node, index, value = n1, 2, 'new_node'
head = insert_node(node, index, value)
