迭代/递归创建链表

Question

需要递归或迭代地为给定的数字字符串创建一个链表。

例如： 数字 = "123" 1 -> 2 -> 3

我写了一个递归函数，但似乎不起作用，它正在创建一个链表但没有中间值。 1 -> 3 而不是 1 -> 2 -> 3

def create_linked_list(head, num):
if num is "":
return head
else:
head.next = ListNode(num[0])
return create_linked_list(head.next, num[1:])
n = "123"
head = ListNode(n[0])
result = create_linked_list(head, n[1:])
while result:
print(result.val)
head = result.next
# This is printing 1 -> 4

这是原始用例

class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
n = "1234"
# I need this part of linked list creation to be done
# in a looping/recursive manner for any kind of number.
l1 = ListNode(n[0])
l1.next = ListNode(n[1])
l1.next.next = ListNode(n[2])
l1.next.next.next = ListNode(n[3])

while l1:
print(l1.val)
head = l1.next
# 1 -> 2 -> 3 -> 4

Answer 1

• 你的递归方法看起来是正确的。您唯一需要做的就是。当您到达数字末尾时，您无需返回头部。因为您已经将头部存储在头部变量中。
• 这是有效的代码。

class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
n = "1234"
def create_linked_list(head, num):
if num is "": #base condition.
return
else:
head.next = ListNode(num[0])
create_linked_list(head.next, num[1:])
head = ListNode(n[0])
temp = head
create_linked_list(head, n[1:])
while temp:
print(temp.val)
temp = temp.next

• 输出

  
  1 2
  3
  4

• 您也可以重写上面的代码，如下所示。

def create_linked_list(head, num):
if num is not "":
head.next = ListNode(num[0])
create_linked_list(head.next, num[1:])

• PS：请记住在使用链表时始终保持清醒
。

Answer 2

递归是一种函数式传统，因此以函数式风格编写程序会产生最佳结果。这意味着我们避免了诸如更改列表节点之类的事情，head.next = ....您的构造函数应该能够同时设置val和next-

class node:
def __init__(self, val, next = None):
self.val = val
self.next = next
def create_llist(v = None, *vals):
if not v:
return None
else:
return node(v, create_llist(*vals))
def llist_to_str(l = None):
if not l:
return "None"
else:
return f"{l.val} -> {llist_to_str(l.next)}"
print(llist_to_str(create_llist(1, 2, 3)))
# 1 -> 2 -> 3 -> None

但是，如果我们将它们作为类的一部分实现，create_llist和llist_to_str可能会更加一致。也许一个更好的名字是llist，对于"链表"——

class llist:
def __init__(self, val, next = None):
self.val = val
self.next = next
def create(v = None, *more):
if not v:
return None
else:
return llist(v, llist.create(*more))
def __str__(self):
return f"{self.val} -> {self.next}"
print(llist.create(1, 2, 3))
# 1 -> 2 -> 3 -> None

函数不依赖于副作用，而是接受输入并产生输出。因此，请注意我们的思想是如何摆脱复杂性的——

class llist:
# ...
def map(node = None, f = lambda x: x):
if not node:
return None
else:
return llist(f(node.val), llist.map(node.next, f))
print(llist.map(llist.create(7, 8, 9), lambda x: x * x))
# 49 -> 64 -> 81 -> None