Как развернуть односвязный список в Python 3?

Question

[whoareyoutofuckinglecture]

Дан односвязный список:

d = {
  'value': 1,
  'next': {
    'value': 2,
    'next': {
      'value': 3,
      'next': {
        'value': 4,
        'next': None,
      },
    },
  },
}

Нужно написать функцию, которая бы выводила элементы данного списка поочерёдно с конца.
Как это можно сделать?

Comments

[longclaps]

Я бы ответил, но у вас такой длинный ник, что я в замешательстве...

[Модератор]

whoareyoutofuckinglecture дорогой пользователь, настоятельно рекомендуем еще раз обратить самое пристальное внимание на п. 3.1 регламента работы сервиса (и, в особенности, на его последний абзац).
В противном случае, ваши вопросы будут удаляться по причине тег-спама, а систематические нарушения приведут к блокировке учетной записи.

Answer 1

[0xD34F]

Рекурсия есть:

def printSinglyLinkedList(node):
  if node != None:
    printSinglyLinkedList(node['next'])
    print(node['value'])


printSinglyLinkedList(d)

Рекурсии нет:

def reverseSinglyLinkedList(head):
  prevNode = None
  currNode = head

  while currNode != None:
    nextNode = currNode['next']
    currNode['next'] = prevNode
    prevNode = currNode
    currNode = nextNode

  return prevNode

Comments

[whoareyoutofuckinglecture]

Спасибо!
А есть ли возможность сделать это без рекурсии, или рекурсия - единственный способ решения?

[Roman K]

whoareyoutofuckinglecture, не единственный и даже не лучший. Потому что глубина стека рекурсии будет равна длине списка, а это очень плохо.

[whoareyoutofuckinglecture]

Roman Kitaev, подскажите, пожалуйста, что мне нужно сделать, чтобы обратить данный односвязный список без рекурсии?
Можно даже без кода, просто скажите, пожалуйста, где мне про это почитать и с помощью чего это делается?
Я так понял, что с использованием словарных методов я эту задачу не решу.
Не знаю, как добраться до следующего 'next'

[0xD34F]

добавил вариант без рекурсии

[whoareyoutofuckinglecture]

0xD34F, большое спасибо вам!!!

Answer 2

[powerind]

С рекурсией но без печати

def recu(d):
    l = []
    if d.get('next') is not None:
        l.append(d.get('value', None))
        l.extend(recu(d['next']))
    else:
        l.append(d.get('value', None))
    return l

Или вот без рекурсии:

def non_recu(d):
    l = []
    while True:
        l.append(d.get('value', None))
        d = d.get('next', None)
        if d is None:
            break
    return l

Воспользоваться можно так:

recu(d)
[1, 2, 3, 4]
non_recu(d)
[1, 2, 3, 4]