Python复制并连接链表,保留顺序

Question

我在python中有一个基本的链表实现.每个Cell都有一些与之关联的数据和下一个对象,用于包括链表的其余部分(如果在构造函数中只给出了第一个数据参数,则为null).

我想将两个列表复制并连接在一起,以便最终产品保留订单并且独立于两个原始列表.

这是我有的:

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

你做了一些奇怪的事情:

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

表明你的细胞是这样的

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

但是做

C = Cell(A)

从不复制任何东西,它只是创建一个具有相同A值的新Cell.

所以,让我们从可以实际复制自身的Cell开始:

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

现在你的结论很简单:

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版本之前添加了一个新的Cell ,以便从最后构建新的列表.