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

Question

我很难弄清楚如何在单链表中的其他节点之间插入一个节点。在上面的解决方案中，我编写了一个额外的 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现在它打印：10, 20, 30, 40, 50 但它应该打印：10, 20, 25, 30, 40, 50。我认为问题出在 insert_in_between2 方法中的这一行：new_node.nextNode = prev_data2.nextNode...因为这两个都打印出无。任何在正确方向上的帮助都会很棒。

Answer 1

#Linked List Program to Add and Delete Node Form Head, Tail, in Between Nodes.

class Node:

    """ Node Class having the data and pointer to the next Node"""

    def __init__(self,value):

        self.value=value

        self.nextnode=None

        

class LinkedList(object):

    """ Linked List Class to point the value and the next nond"""

    def __init__(self):

        self.head=None

    #Adding Node to the head of linked List

    def head_node(self,value):

        node=Node(value)

        if self.head is None:

            self.head=node

            return

        crnt_node=node

        crnt_node.nextnode=self.head

        self.head=crnt_node

    # Adding New Node in between Node After the Previous Node

    def in_bw_node(self,prev_data,value):

        if prev_data is None:

            print('Can not add nodes in between of empty LinkedList')

            return

        n=self.head 

        while n is not None:

            if n.value==prev_data:

                break

            n=n.nextnode

        new_node=Node(value)

        new_node.nextnode=n.nextnode

        n.nextnode=new_node

    # Adding New Node in between Node before the Previous Node  

    def insert_before_node(self,prev_data,value):

        if prev_data is None:

            print('Can not add nodes in between of empty LinkedList')

            return

        p=self.head     

        new_node=Node(value)

        while p is not None:

            if p.nextnode.value==prev_data:

                break

            p=p.nextnode

        new_node.nextnode=p.nextnode

        p.nextnode=new_node

    # Adding New Node in the last and last node is pointting to None

    def tail_node(self,value):

        node=Node(value)

        if self.head is None:

            self.head=node

            return 

        crnt_node=self.head

        while True:

            if crnt_node.nextnode is None:

                crnt_node.nextnode=node

                break

            crnt_node=crnt_node.nextnode

    # Deleting head node(1'st Node ) of the Linked List

    def del_head_node(self):

        if self.head is None:

            print('Can not delete Nodes from Empty Linked List')

            return

        crnt_node=self.head

        while self.head is not None:

            self.head=crnt_node.nextnode

            break

        crnt_node.nextnode=self.head.nextnode

    # Deleting the last Node of the linked List

    def del_tail_node(self):

        if self.head is None:

            print('Can not delete Nodes from Empty Linked List')

            return

        crnt_node=self.head

        while True:

            if crnt_node.nextnode.nextnode is None:

                crnt_node.nextnode=None

                break

            crnt_node=crnt_node.nextnode

    # Deleting the Node after given Node

    def del_in_bw_node(self,value):

        del_node=Node(value)

        if self.head is None:

            print('Can not delete Nodes from Empty Linked List')

            return

        crnt_node=self.head

        while  True:

            if crnt_node.value==del_node.value:

                break

            prev=crnt_node

            crnt_node=prev.nextnode

        prev.nextnode=crnt_node.nextnode

            

    # Method to print the Data

    def print_list(self):

        crnt_node=self.head

        while crnt_node is not None:

            print(crnt_node.value,end='->')         

            crnt_node=crnt_node.nextnode

        print('None')

llist=LinkedList()

llist.print_list()

llist.head_node(1)

llist.print_list()

llist.tail_node(2)

llist.print_list()

llist.tail_node(5)

llist.print_list()

llist.tail_node(10)

llist.print_list()

llist.head_node(25)

llist.print_list()

llist.in_bw_node(5,7)

llist.print_list()

llist.insert_before_node(5,3)

llist.print_list()

llist.del_head_node()

llist.print_list()

llist.del_tail_node()

llist.print_list()

llist.del_in_bw_node(5)

llist.print_list()