Python连接链表

Question

我试图将Python链表连接起来，而不复制其中包含的节点数据。我有一个函数会使用传入的节点副本连接列表，但我似乎无法让不使用副本的函数工作起来。

这些函数仅供测试和计时目的；我知道Python内置的列表非常棒！

以下是我使用的类和连接函数。

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

def print_list(self):
    node = self
    while node != None:
        print node.data
        node = node.next

连接函数不应作为Cell类的成员函数。

def list_concat(A, B):
    while A.next != None:
        A = A.next
    A.next = B      
    return A

如果参数A拥有超过一个节点，这个函数会重写列表的第一个元素。我理解为什么会发生这种情况，但是不确定如何解决。

以下是我一直在使用该函数进行测试的代码。

e = Cell(5)
test = Cell(3, Cell(4))
test2 = list_concat(test2, e)   
test2.print_list()

任何见解或帮助都将不胜感激。

*编辑以修复代码格式。

- Christian Benincasa

---

你的连接函数应该能够正常工作。请注意，list 不是一个链表。我建议你看一下 Lisp 的实现，因为它们使用与你相同结构的单元格。 - Marcin

我认为这个实现应该也能工作，但是当我打印列表（test2）时，它将元素列为4->5->None，而应该列为3->4->5->None。 - Christian Benincasa

请注意，在您的代码示例中，您在分配之前将test2用作参数。 - Marcin

这个需要加上作业标签吗？ - kͩeͣmͮpͥ ͩ

Answer 1

尝试使用以下方法代替：

def list_concat(A, B):
    current = A
    while current.next != None:
        current = current.next
    current.next = B
    return A

给函数参数赋新值是一种糟糕的编程实践，而您所提供的代码也说明了这一点：您使用A来迭代原始列表，这样做会导致您丢失对其第一个元素的引用。

- Óscar López

---

另一种可能性是将“查找列表末尾”的部分拆分为一个单独的函数，该函数返回最后一个节点。然后它就是 list_concat(A, B): find_end(A).next = B; return A。 - kindall

或者，我感到惭愧的是刚才才想到，就像Python内置的list类一样，根本不返回列表。 - kindall

Answer 2

我不确定extend是否执行复制操作，但如果没有，请使用

A.extend(B)

- Chris

---

抱歉，我错过了你说的这是为测试目的而进行的部分。 - Chris