Как вставить узел между другим узлом в связанном списке? - PullRequest
Новая
       40

Как вставить узел между другим узлом в связанном списке?

0 голосов
/ 25 декабря 2018

Я возвращаюсь к вопросу, который я опубликовал некоторое время назад и разместил здесь: LinkedList - вставка между узлами не вставляется

Мне трудно понять, как вставить узелмежду другими узлами в односвязном списке.В приведенном выше решении я написал дополнительный метод getNodes, который превращает данные в узел и помещает их между узлами, но это значительно увеличивает временную сложность.Должен быть способ вставки между узлами без использования этого пользовательского метода, но я просто не могу понять, как.

Вот мой новый код: 

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

    def __str__(self):
        return str(self.data)


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


    def insert_in_between2(self, data, prev_data):
        # instantiate the new node
        new_node = Node(data)
        # assign to head
        thisval = self.head
        # check each value in linked list against prev_data as long as value is not empty
        prev_data2 = Node(prev_data)
        while thisval is not None:
            # if value is equal to prev_data 
            if thisval.data == prev_data2.data:
                print("thisval.data == prev_data.data")
                # make the new node's next point to the previous node's next
                new_node.nextNode = prev_data2.nextNode
                # make the previous node point to new node
                prev_data2.nextNode = new_node
                break
            # if value is not eqaul to prev_data then assign variable to next Node
            else:
                thisval = thisval.nextNode


    def push_from_head(self, NewVal):
        new_node = Node(NewVal)
        print("This is new_node: ", new_node.data)
        last = self.head
        print("This is last/HEAD: ", last)
        if last is None:
            print("Head is NONE")
            self.head = new_node
            print("This is self.head: ", self.head)
            return
        print("last.nextNode: ", last.nextNode)
        while last.nextNode is not None:
            print("this is last inside while loop: ", last.data)
            print("last.nextNode is not NONE")
            last = last.nextNode
            print("This is the last last: ", last.data)
        last.nextNode = new_node
        print("This is last.nextNode: ", last.nextNode)


    def print_nodes(self):
        if self.head:
            thisval = self.head

            while thisval:
                print("This is node: ", thisval.data)
                thisval = thisval.nextNode


e1 = LinkedList()

e1.push_from_head(10)
e1.push_from_head(20)
e1.push_from_head(30)
e1.push_from_head(40)
e1.push_from_head(50)

e1.insert_in_between2(25, 20)
# print("This is the index: ", e1.getNode(1))
e1.print_nodes()

Сейчас он печатает: 10, 20, 30, 40, 50, но предполагается вывести: 10, 20, 25, 30, 40, 50.

Я думаю, что проблема в этой строке в методе insert_in_between2: 

new_node.nextNode = prev_data2.nextNode

... потому что оба они печатают None.Любая помощь в правильном направлении была бы великолепна.

1 Ответ

0 голосов
/ 25 декабря 2018

Вы создаете новый узел, который не является частью списка со строкой: 

prev_data2 = Node(prev_data)

prev_data кажется значением, которое вы ищете, из которого вы хотите вставить изof.

Затем вы подключаете к этому свой новый узел, но поскольку он не является частью списка, он как бы осиротел.Вам не нужен этот узел.Просто подключите ваш новый узел к тому, который вы только что нашли: 

while thisval is not None:
    if thisval.data == prev_data:             # you found the node before the insert
        new_node.nextNode = thisval.nextNode  # new node's next gos to found node's next 
        thisval.nextNode = new_node           # found node's next goes to new node
...