Итеративно / Рекурсивно создайте связанный список

Question

Необходимо рекурсивно или итеративно создать связанный список для заданной числовой строки.

Например: Number = "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

• Ваш рекурсивный подход выглядит правильно. Единственное, что вам нужно сделать, это. вам не нужно возвращать голову, когда вы достигнете конца номера. Потому что вы уже храните head в переменной head.
• Вот код, который работает.

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