代码之家 › 专栏 › 技术社区 › Sook Lim

在python中向链表实现添加递归复制方法?

linked-list recursion python

Sook Lim · 技术社区 · 8 年前

嗨,我用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)

有人能帮我解释一下吗?任何帮助都将不胜感激谢谢!

编辑:好吧,很明显它会先插入最后一项?为什么会这样?

2 回复 | 直到 8 年前

Marco Aurélio Falcão 8 年前

1-调用index等于零的insert时,将列表项插入到前面,即head所指的位置(请参见方法def insert(self,index,item): 2-当调用方法副本时,将递归调用方法def_copy_aux_(self,node,new_list):直到到达列表的最后一项,该项的node.next等于none。 3-之后,在每次从方法copy_aux返回之后,它开始将itens从最后一个项插入到第一个项前面的新列表中,从而给出正确的顺序。

我建议使用打印来跟踪列表复制递归,如下所示:

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

Ajax1234 8 年前

我建议将列表平展,然后将值重新插入到新列表中:

class LinkedList:
   def __init__(self, value = None):
     self.head = value
     self._next = None
   def insert_node(self, _val):
     if self.head is None:
       self.head = _val   
     else:
       getattr(self._next, 'insert_node', lambda x:setattr(self, '_next', LinkedList(x)))(_val)
   def flatten(self):
     return [self.head, *getattr(self._next, 'flatten', lambda :[])()]
   @classmethod
   def copy(cls, l):
      t = cls()
      for i in l.flatten():
        t.insert_node(i)
      return t

l = LinkedList()
for i in range(10):
  l.insert_node(i)
new_l = LinkedList.copy(l)