Python 复制并连接链表，保持顺序

Question

我在用Python实现一个简单的链表。每个Cell都有一些数据和一个指向下一个对象的链接，这个链接用来连接链表的其余部分。如果在构造函数中只给了第一个数据参数，链接就会是空的。

我想把两个链表复制并连接在一起，最终的结果要保持原来的顺序，并且和这两个原始链表没有关系。

这是我现在的代码：

def list_concat_copy(A, B):
        C = Cell(A)
        while A.next != None:
                A = A.next
                C = Cell(A,C)
        C = Cell(B,C)
        while B.next != None:
                B = B.next
                C = Cell(B,C)
        return C

我遇到的问题是，这样做会把顺序搞反：

A = Cell(8,Cell(9,Cell(10)))
B = Cell(11,Cell(12,Cell(13)))
C = list_concat_copy(A,B)

现在如果我用walk_and_print(C)去打印，就会得到13 12 11 10 9 8。

有没有什么想法？

Answer 1

我觉得在没有看到Cell的定义的情况下，回答这个问题有点困难，不过我想我看到了错误所在。可以把这个列表想象成一层层的结构。循环从C的最里面的值开始。每次在循环中调用Cell时，它会用下一个值再“包裹”一次这个值。最外层的Cell包含的是最后一个值。

换句话说，

C = Cell(8)
D = Cell(9, C)
E = Cell(10, D)

相当于

E = Cell(10, Cell(9, Cell(8)))

这样说清楚了吗？

补充一下：

为了完整起见，这里还有另一种做法：

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

def list_concat_copy(A, B):
        head = Cell(A.data)
        C = head
        while A.next != None:
                A = A.next
                C.next = Cell(A.data)
                C = C.next
        C.next = Cell(B.data)
        C = C.next
        while B.next != None:
                B = B.next
                C.next = Cell(B.data)
                C = C.next
        return head


A = Cell(8, Cell(9, Cell(10)))
B = Cell(11, Cell(12, Cell(13)))
C = list_concat_copy(A, B)

Answer 2

这些列表打印出来是反向的，因为你在把外层元素放进新列表的时候，是先放的外层元素。然后在继续展开A的时候，你又给C加了一层包装。

复制这些列表最简单的方法可能是对A和B做一个深拷贝（我们称它们为C和D），然后找到C中最深的元素（通过一直遍历到C.next==None），把它设置为指向D。

Answer 3

你做了一些奇怪的事情：

A = Cell(8,Cell(9,Cell(10)))

这表明你的单元格（Cell）大概是这样的：

class Cell(object):
    def __init__(self, val, nxt=None):
        self.val = val
        self.next = nxt

但是执行

C = Cell(A)

并不会复制任何东西，它只是创建了一个新的单元格，值和原来的单元格一样。

那么，我们先来看看一个可以真正复制自己的单元格：

class Cell(object):
    def __init__(self, val, nxt=None):
        self.val = val
        self.next = nxt

    def copy(self):
        if self.next is None:
            return Cell(self.value)
        else:
            return Cell(self.value, self.next.copy())

现在你的连接（concat）就简单多了：

def concat_copy(a, b):
        new = a.copy()

        # find the end of the copy
        last = new
        while last.next is not None:
            last = last.next
        # append a copy of the other list
        last.next = b.copy()

为了完整性，这里是你尝试做的事情：

def copy( cells ):
    new = Cell(cells.value)
    current = new
    old = cells

    while old.next is not None:
        # copy the current cell
        ccopy = Cell(old.value)

        # add it
        current.next = ccopy

        # prepare for the next round
        current = ccopy
        old = old.next

    return new

我觉得这有助于理解你是如何不小心把单元格反转的：你是从前往后遍历列表，但 C = Cell(A,C) 这个操作是在旧的 C 前面放了一个新的单元格，所以这样就从后面开始构建了新的列表。