我想通过递归反转链表中数字的顺序。
(1,(2,(3,( )))) ----> (3,(2,(1,( ))))
我的链接列表是嵌套元组。 First(xs) 返回第一个元素,在上面的示例中,它可能是右侧的 1 或 3。 Rest(xs) 返回右侧的所有其他元素 (2,(3,( ))) 或 (2,(1,( ))。
我的代码如下所示:
empty = ()
def reversed(xs):
if xs == (first(xs), empty):
return first(xs)
else:
return reversed(rest(xs)), first(xs)
但它会产生以下输出:
((3, 2), 1)
我想,我已经很接近了,但我已经不知道如何解决这个问题了。
有人可以帮助我吗?
谢谢
最佳答案
有不同的方法可以做到这一点。现在,您只是将它们连接到一个新元组,这不会创建正确形成的链接列表。相反,您可以使用第二个函数将前一个 first
附加到 reversed
rest
上。另外,您的基本情况似乎是错误的,因为您仅返回单个元素而不是链接列表。
def reversed(xs):
if xs == empty:
return empty
else:
return append(reversed(rest(xs)), first(xs))
def append(xs, x):
if xs == empty:
return (x, empty)
else:
return first(xs), append(rest(xs), x)
>>> reversed((1, (2, (3, (4, empty)))))
(4, (3, (2, (1, ()))))
但是请注意,这具有二次复杂度 O(n²),因为您必须迭代整个列表(或部分列表)以附加
每个中的第一个
节点reversed
函数的步骤。对于线性复杂度 O(n) 版本,您可以向 reversed
函数添加第二个参数(或者,如果无法更改签名,则创建由原始函数调用的第二个函数)。这将在第二个参数中构建反向列表,最后仅返回该列表。
def reversed(xs, tail=empty):
if xs == empty:
return tail
else:
return reversed(rest(xs), (first(xs), tail))
此外,正如评论中所指出的,有比 Python 更好的语言来定义递归数据结构,并且有更好的方法在 Python 中使用列表,但我假设这只是为了学习而不是为了实际使用。
关于python - 递归地颠倒链表中数字的顺序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54534488/