将列表转换为链表

Question

我想弄清楚将列表转换为链接列表。我已经有一个链接类，但我正在尝试弄清楚如何将列表转换为链接列表，例如：

def list_to_link(lst):
    """Takes a Python list and returns a Link with the same elements.

    >>> link = list_to_link([1, 2, 3])
    >>> print_link(link)
    <1 2 3>
    """


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 print_link(link):
    """Print elements of a linked list link."""

    >>> link = Link(1, Link(2, Link(3)))
    >>> print_link(link)
    <1 2 3>
    >>> link1 = Link(1, Link(Link(2), Link(3)))
    >>> print_link(link1)
    <1 <2> 3>
    >>> link1 = Link(3, Link(Link(4), Link(5, Link(6))))
    >>> print_link(link1)
    <3 <4> 5 6>
    """
    print('<' +helper(link).rstrip() +'>')

Answer 1

我有一个使用虚拟 ListNode 的想法。这使得代码简单而整洁。

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


def lst2link(lst):
    cur = dummy = ListNode(0)
    for e in lst:
        cur.next = ListNode(e)
        cur = cur.next
    return dummy.next

Answer 2

马特的答案很好，但它超出了上述问题中描述的函数原型的约束。

阅读摘要/原型，问题的创建者似乎想用递归/动态编程方法来解决这个问题。这是一个非常标准的递归算法介绍。它更多的是了解如何编写优雅的递归代码，而不是在 Python 中创建链表（不是真正有用或常见）。

这是我想出的一个解决方案。试试看：

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 print_link(link):
    """Print elements of a linked list link.
    """
    print('<' + helper(link).rstrip() +'>')


def list_to_link(lst):
    """Takes a Python list and returns a Link with the same elements.
    """
    if len(lst) == 1:
        return Link(lst[0])
    return Link(lst[0], list_to_link(lst[1:]))  # <<<< RECURSIVE

def helper(link):
    if isinstance(link.first, Link):
        first = '<' + helper(link.first).rstrip() + '>'  # <<<< RECURSIVE
    else:
        first = str(link.first)

    if link.rest != Link.empty:
        return first + ' ' + helper(link.rest)  # <<<< RECURSIVE
    else:
        return first + ' '

def main():
    """ Below are taken from sample in function prototype comments
    """
    link = list_to_link([1, 2, 3])
    print_link(link)

    link = Link(1, Link(2, Link(3)))
    print_link(link)
    link1 = Link(1, Link(Link(2), Link(3)))
    print_link(link1)
    link1 = Link(3, Link(Link(4), Link(5, Link(6))))
    print_link(link1)


if __name__ == '__main__':
    main()