在给定位置插入节点

Question

我正在学习python和数据结构。我实现的是单链表方法，包括在头部和指定位置插入。最后我写了这个代码：

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

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

    def insertathead(self,new_data) :
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node


    def InsertNpos(self,new_data,pos):
        start = self.head
        if pos == 0:
            return Node(new_data, self.head)
        while pos > 1:
            self.head = self.head.next
            pos -= 1
        self.head.next = Node(new_data, self.head.next)
        return start

    def PrintLinkList(self) :
        temp = self.head
        while (temp) :
            print (temp.data)
            temp = temp.next

if __name__ == '__main__' :
   llist = LinkedList()
   llist.insertathead(8)
   llist.insertathead(3)     
   llist.insertathead(10)
   llist.insertathead(12)
   llist.insertathead(15)
   llist.insertathead(2)
   llist.InsertNpos(1,2)
   llist.PrintLinkList()

输出：

^{pr2}$

现在，只需在头部插入就可以了，但是InsertNpos（1,2）给出了错误的输出。输出应该是2,15,1,12,10,3,8。请告诉我我的代码哪里出错了。在

Answer 1

尽管答案已经被接受，我还是尝试了这个解决方案，正如AChampion所说，在0处插入对我来说不起作用，但我的解决方案做到了：

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

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

    def insertathead(self,new_data) :
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node


    def InsertNpos(self,new_data,pos):
        if pos == 0:
            self.head = Node(new_data, self.head)
            return self.head
        i = 0
        curr = self.head
        while curr.next:
            if i == pos - 1:
                curr.next = Node(new_data, curr.next)
                return self.head
            curr = curr.next
            i += 1
        curr.next = Node(new_data)
        return self.head

    def PrintLinkList(self) :
        temp = self.head
        while (temp) :
            print (temp.data)
            temp = temp.next

如果pos超出范围，这将在末尾插入项。在

Answer 2

def insertNodeAtPosition(head, data, position):
    current = head
    if not head:
        head = SinglyLinkedListNode(data)
        return head

    # Shift to element before position i.e. before_node
    # Change it to point to new_node
    # Set new_node.next to before_node.next
    for _ in range(position-1):
        current = current.next

    temp = current.next
    new_node = SinglyLinkedListNode(data)
    current.next = new_node
    new_node.next = temp

    return head

Answer 3

当您在位置pos插入时，您的插入例程会删除列表的第一个pos-1元素。它在每次迭代中都会改变头指针。您需要一个局部变量来迭代列表。另外，为什么要返回值？你从不使用它。此方法的唯一目的是更新列表。在

def InsertNpos(self,new_data,pos):
    if pos == 0:
        self.head = Node(new_data, self.head)
        return

    start = self.head
    while pos > 1:
        start = start.next
        pos -= 1
    start.next = Node(new_data, start.next)

新输出：

^{pr2}$