Объединение связанных списков итеративно

Question

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

class Link: 
    empty =() 

    def __init__(self, first, rest=empty): 
     assert rest is Link.empty or isinstance(rest, Link) 
     self.first = first 
     self.rest = rest 

    def __add__(self, lst): 
     """ 
     >>>s = Link(1, Link(2)) 
     >>>s + Link(3,Link(4)) 
     Link(1,Link(2,Link(3,Link(4)))) 
     """ 
     result = Link.empty 
     while self is not Link.empty: 
      result = Link(self.first,result) 
      self = self.rest 

     while lst is not Link.empty: 
      result = Link(lst.first, result) 
      lst = lst.rest 
     return result 

Answer 1

Избегайте изменения self, найти конец первого списка, и добавить второй список к нему.

def __add__(self, lst): 
    current = self 

    while current.rest != self.empty: 
     current = current.rest 

    current.rest = lst 

    return self 

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

def __add__(self, lst): 
    new_list = Link(self.first) 
    new_link = new_list 

    current = self 

    while current.rest != self.empty: 
     new_link.rest = Link(current.first) 
     new_link = new_link.rest 

     current = current.rest 

    current = lst 

    while current != self.empty: 
     new_link.rest = Link(current.first) 
     new_link = new_link.rest 

     current = current.rest 

    return new_list 

Примечания: это будет делать ссылки на каждый Link.first значения (не независимые копии).

Answer 2

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

Я предполагаю, что вы хотите метод __add__, чтобы создать копию, составленную из self с последующим lst, так просто создавать копии Link с от self первого, а затем lst и прикрепить их, как вы итерацию. Вроде так:

def __add__(self, lst): 
    result = Link(self.first) 
    cur = result 
    self = self.rest 
    # Copy our list 
    while self is not Link.empty: 
     cur.rest = Link(self.first) 
     cur = cur.rest 
     self = self.rest 
    # Copy and connect the Links in lst 
    while lst is not Link.empty: 
     cur.rest = Link(lst.first) 
     cur = cur.rest 
     lst = lst.rest 
    return result 

Чтобы определить, что не так с текущим кодом, рассмотрите пример с примером. Предположите, self является Link(1,Link(2)).

result = Link.empty 
    while self is not Link.empty: 
     result = Link(self.first,result) 

Что такое result?

• Link(self.first,result)

• является Link(1, Link.empty)

  self = self.rest 
  

Теперь self является Link(2,())

 result = Link(self.first,result) 

Что result сейчас?

• Link(self.first,result)
• является Link(2, Link(1, Link.empty))

К сожалению. Нашел проблему; вы соединяете ссылки в обратном порядке.