python - 使用递归从列表创建链表

Question

如何使用递归来获取随机值列表并使其成为链表？其中每个值都是一个节点。截至目前，我已经尝试实施以下...

def pyListToMyList(pylst):
        lists = mkMyList()
        lists.head = pyListToMyListRec(pylst)
        return lists

def pyListToMyList(pylst):            
        if pylst:
                return mkEmptyNode()
        else:
                return mkNode(pylst[0], pyLstToMyListRec(pylst[1:]))

问题是 else 语句返回错误，指出索引超出范围。

Answer 1

def pyListToMyList(pylst):            
    if not pylst:
        return mkEmptyNode()
    else:
        return mkNode(pylst[0], pyLstToMyListRec(pylst[1:]))

编辑：虽然这是 O(n^2) 因为所有的列表复制。

我会做

def pyListToMyList(pylst, i=0):
    if i > len(pylst):
        return mkEmptyNode()
    else:
        return mkNode(pylst[i], pyLstToMyListRec(pylst, i+1))

甚至更高效且不太可能溢出堆栈（尽管这不使用递归）：

def pyListToMyList(pylst):
    lst = mkEmptyNode()
    for x in reversed(pylist):
        lst = mkNode(x, lst)
    return lst