以多个链表作为参数的递归替代/合并链表函数？

Question

我在使用带有多个链接列表参数的递归链接列表函数时遇到了问题。

到目前为止，我已经提出了以下，一个单一的链接列表和工作良好。

def recursive_ll(ll):
    if ll == None:
        return None
    elif ll.next == None:
        return LN(ll.value)
    else:
        return_ll = LN(ll.value, recursive_ll(ll.next))
        if return_ll.value == return_ll.next.value:
            return_ll = return_ll.next
    return return_ll 

结果将是：

ll = list_to_ll(['x','g','f','n'])
print(str_ll(recursive_ll(ll)))

x->g->f->n->None

但是我真的很困惑如何用多个链表作为参数来创建递归链表函数。

例如，def recursive_ll(ll)：将是def recursive_ll(ll，ll2)：

返回的结果是

ll = recursive_ll(['a','x','b','e'])
ll2 = recursive_ll(['d','f','m'])

a->d->x->f->b->m->e->None

再一次，从两个链接列表中得出以下期望的结果：

a->d->x->f->b->m->e->None

如有任何帮助或建议，将不胜感激！

Answer 1

您应该使用类而不是简单的函数作为帮助。并接受任何可迭代的链接列表的源。如果在链接列表类上实现迭代器，则允许在任何可迭代列表和链接列表之间进行简单的转换。

链接列表类可以是：

class LL:
    class iter:
        def __init__(self, ll):
            self.cur = ll.front
        def __iter__(self):
            return self
        def __next__(self):
            if self.cur is None:
                raise StopIteration()
            val = self.cur.value
            self.cur = self.cur.next
            return val

    def __init__(self, l):
        self.front = last = None
        for v in l:
            ln = LN(v)
            if last is None:
                self.front = ln
            else:
                last.next = ln
            last = ln

    def __str__(self):
        answer = ''
        for val in self.iter_elt():
            answer += str(val) + '->'
        return answer + 'None'

    def __repr__(self):
        return str(self.__class__) + ':' + str(self)

    def __iter__(self):
        return LL.iter(self)

这立即允许：

>>> print(LL('abcd'))
a->b->c->d->None
>>> list(LL('abcd'))
['a', 'b', 'c', 'd']

完成后，您可以将递归链接列表声明为链接列表的子类，该子类允许在包含链接列表的情况下提取合并顺序中的元素。

首先，应该在iter_elt类中添加一个新方法LL，它只调用iter，并在__str__中使用它来简化子类：

class LL:
    ...
    def __str__(self):
        answer = ''
        for val in self.iter_elt():
            answer += str(val) + '->'
        return answer + 'None'
    ...
    def iter_elt(self):
        return self.__iter__()

因为现在，在RLL中覆盖iter_elt就足够了，并且构建一个迭代器来扫描它的子列表，如果可能的话，在它们上反复调用iter_elt，直到所有的迭代器都用完为止。代码可以是：

class RLL(LL):
    class iter:
        def __init__(self, rll):
            self.iters = LL(i.iter_elt() if hasattr(i, 'iter_elt') else iter(i)
                            for i in rll)
            self.cur = self.iters.front
            self.prev = None
        def __iter__(self):
            return self
        def __next__(self):
            try:
                elt = next(self.cur.value)
                self.prev = self.cur
                self.cur = self.cur.next
                if self.cur is None:
                    self.cur = self.iters.front
                    self.prev = None
            except StopIteration:
                self.cur = self.cur.next
                if self.cur is None:
                    if self.prev is None:
                        raise
                    self.cur = self.iters.front
                    self.prev = None
                else:
                    if self.prev is None:
                        self.iters.front = self.cur
                    else:
                        self.prev.next = self.cur
                elt = self.__next__()
            return elt

    def iter_elt(self):
        return RLL.iter(self)

Answer 2

我完全同意@Serge的观点，您应该创建一个LinkedList类来完成这个任务，下面是您所做事情的过程方式。

还要注意的是，它不是递归完成的，而是“吡咯烷酮”。

from itertools import chain, zip_longest

class LN:
    def __init__(self, value, next=None):
        self.value = value
        self.next  = next

def list_to_ll(l):
    if l == []:
        return None
    front = rear = LN(l[0])
    for v in l[1:]:
        rear.next = LN(v)
        rear = rear.next
    return front

def iterate(ll):
    while ll is not None:
        yield ll.value
        ll = ll.next

def str_ll(ll):
    return '->'.join(str(v) for v in iterate(ll)) + '->None'

def alternate(ll_1, ll_2):
    _NULL = object()
    chained = chain.from_iterable(zip_longest(iterate(ll_1), iterate(ll_2), 
                                              fillvalue=_NULL))
    return list_to_ll(list(v for v in chained if v is not _NULL))

if __name__ == '__main__':

    ll_1 = list_to_ll(['a','x','b','e'])
    ll_2 = list_to_ll(['d','f','m'])

    print(str_ll(alternate(ll_1, ll_2)))  # -> a->d->x->f->b->m->e->None