以迭代方式组合链表

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

从概念上讲，要合并两个链表，您需要做的就是找到第一个列表的尾部，并将其与第二个列表的头部连接，然后返回第一个列表的头部。当前代码的主要问题是你没有保持在第一个列表的头部。

我假设您希望 __add__ 方法创建一个由self后跟 lst 组成的副本，因此只需先从self创建 Link 的副本，然后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))

哎呀。发现问题;您正在反向连接链接。

Answer 2

避免更改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值（不是独立副本）。