python - Combining linked lists iteratively -

i'm trying combine 2 linked lists iteratively, have right giving me reverse of result. there way combine lists in correct order without having reverse if after result list created?

class link:      empty = ()      def __init__(self, first, rest=empty):         assert rest 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 not link.empty:              result = link(self.first,result)             self = self.rest           while lst not link.empty:              result = link(lst.first, result)             lst = lst.rest          return result  

conceptually, combine 2 linked lists, need find tail of first list, , connect head of second list, , return head of first list. major problem current code not keep around head of first list.

i'm assuming want __add__ method create copy made of self followed lst, create copies of links self first , lst , attach them iterate. so:

def __add__(self, lst):     result = link(self.first)     cur = result     self = self.rest     # copy our list     while self not link.empty:         cur.rest = link(self.first)         cur = cur.rest         self = self.rest     # copy , connect links in lst     while lst not link.empty:         cur.rest = link(lst.first)         cur = cur.rest         lst = lst.rest     return result 

to diagnose what's wrong current code, consider stepping through example. assume self link(1,link(2)).

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

what's result now?

• link(self.first,result)

• is link(1, link.empty)

      self = self.rest 

now self link(2,())

        result = link(self.first,result) 

what's result now?

• link(self.first,result)
• is link(2, link(1, link.empty))

oops. found problem; connecting links in reverse.