在给定位置插入节点

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()

输出：

15
1
12
10
3
8

现在，只是在头部插入工作正常，但 InsertNpos(1,2( 给出了错误的输出。输出应该是 2,15,1,12,10,3,8.请告诉我我的代码哪里出错了。

Answer 1

当您插入位置位置时，插入例程将删除列表中的第一个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)

新输出：

Before insertion
2
15
12
10
3
8
After  insertion
2
15
1
12
10
3
8

Answer 2

尽管答案已经被接受，但我还是尝试了该解决方案，并且正如 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 3

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