如何在链接列表中的另一个节点之间插入节点？

Question

我正在重新审视我前一段时间发布的问题: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

...因为这两个都打印出无.任何正确方向的帮助都会很棒.

Answer 1

您正在使用以下行创建一个不属于列表的新节点：

prev_data2 = Node(prev_data)

prev_data似乎是您正在搜索的要插入 from 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