Python copies and merges linked lists, keeps order

Question

I have a basic implementation of linked lists in python. Each Cellhas some data associated with it, and the next object used to include the rest of the linked list (and null if only the first data parameter is specified in the constructor).

I want to copy and merge the two lists together so that the final product remains in order and is independent of the two source lists.

Here is what I have:

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

The problem I am facing is that this is undoing the order:

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

Now, if I walk_and_print(C), I get13 12 11 10 9 8

Any thoughts?

Answer 1

You do some weird things:

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

assumes your cell is like

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

C = Cell(A)

, A, .

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

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, .

Answer 2

, OUTER FIRST. A, C.

, deepcopy A B ( C D), C ( C.next == None) 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))