Копирование Python и объединение связанных списков, сохранение порядка

Question

У меня есть базовая реализация связанного списка в Python. Каждый Cell имеет некоторые данные, связанные с ним и следующим объектом, который используется для включения остальной части связанного списка (и ноль, если в конструкторе указан только первый параметр данных).

Я хочу скопировать и объединить два списка вместе, чтобы конечный продукт сохранил порядок и не зависел от двух исходных списков.

Вот что у меня есть:

<code>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

У меня проблема в том, что это меняет порядок:

<code>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, что и для значения.

Итак, давайте начнем с ячейки, которая на самом деле может копировать себя:

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, так что строится новый список с конца.

Answer 2

Списки распечатываются в обратном направлении, потому что, когда вы упаковываете элементы OUTER в новый список FIRST.Продолжая развертывать A, вы добавляете перенос к C.

. Самый простой способ дублировать эти списки - сделать deepcopy для A и B (назовем их Cи D), а затем установите самый глубокий элемент в C (найденный путем обхода до C.next == Нет) для ссылки D.

Answer 3

Я чувствую, что немного трудно ответить на этот вопрос, не видя определения Cell - но я думаю, что вижу ошибку. Думайте о списке как о наборе слоев. Цикл начинается с самого внутреннего значения C. Каждый раз, когда вы вызываете Cell в цикле, он «оборачивает» это значение другим 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 4

Попробуйте это:

def list_concat(x,y):
    if x.next is None:
        return Cell(x.data,y)
    else:
        return Cell(x.data,list_concat(x.next,y))