python - 将递归复制方法添加到 Python 中的链表实现？

Question

嗨，我在 Python 中实现了一个链表，我得到了这段代码，可以将链表复制到另一个链表，但我不明白为什么它插入到 0 索引处？

那么复制的列表不会被颠倒吗？但是我尝试运行它并且输出是正确的并且是有序的？

我的插入功能

def insert(self, index, item):
    if index<0 and index<-1*len(self):
        raise IndexError("Negative index out of range")
    elif index>0 and index>=len(self):
        raise IndexError("Positive index out of range")

    if index==0:
        self.head=Node(item,self.head)

    elif index>0:
        node=self._get_node(index-1)
        node.next=Node(item,node.next)

    else:
        node=self._get_node(index+len(self))
        node.next=Node(item,node.next)
    self.count+=1

我的复制功能

 def copy(self):
    new_list=linkedList()
    self._copy_aux_(self.head,new_list)
    return new_list

 def _copy_aux_(self, node, new_list):
    if node is not None:
        self._copy_aux_(node.next, new_list)
        new_list.insert(0,node.item)

有人可以帮忙解释一下吗？任何帮助将不胜感激，谢谢！

编辑：好吧，显然它首先插入最后一项？为什么会这样？

标签： pythonrecursionlinked-list

Answer 1

1 - 当您调用索引等于零的插入时，您会预先插入列表项，即在 head 指向的位置（参见方法 def insert(self, index, item): 2 - 当方法副本被调用时def _copy_aux_(self, node, new_list)：递归调用，直到到达列表的最后一项，它的node.next等于None。 3 - 之后，从方法_copy_aux_每次返回后，它开始插入itens在 new_list 前面从最后一项到第一项，它给出了正确的顺序。

我建议包括打印来跟踪列表复制递归，如下面的代码：

def copy(self):
        print('Trace copy:')
        new_list=linkedList()
        self._copy_aux_(self.head,new_list)
        return new_list

    def _copy_aux(self, node, new_list):
        if node is not None:
            self._copy_aux_(node.next, new_list)
            new_list.insert(0,node.item)
            print(new_list)

然后运行以下示例（取自https://repl.it/@MuhammadFermi/week8-2）：

list = linkedList()
list.insert(0, 3)
list.insert(0, 9)
list.insert(0, 2)
list.insert(0, 5)
list.insert(0, 1)
list.insert(2, 6)
list.insert(10, 7)
print(list)
print(len(list))
print(3 in list)
list2 = list.copy()
print('list2 =')
print(list2)

您应该得到以下结果：

1, 5, 6, 2, 9, 3, 7, 
7
True
Trace copy:
7, 
3, 7, 
9, 3, 7, 
2, 9, 3, 7, 
6, 2, 9, 3, 7, 
5, 6, 2, 9, 3, 7, 
1, 5, 6, 2, 9, 3, 7, 
list2 =
1, 5, 6, 2, 9, 3, 7, 

Process finished with exit code 0