Одиночный список не реверсируется при использовании рекурсии

Question

У меня возникли проблемы с выяснением того, чего не хватает. Я просмотрел несколько других решений в Интернете, и они не работают, когда я применяю эти различия. Я потратил много времени на отладку. Вот мой код:

def recurse_reverse(self, curr, level): 
    print('-' * level, 'curr:', curr.value, '| next:', curr.next.value if curr.next else curr.next) 
    if (not curr) or (not curr.next): # if there's 0 or 1 node 
     return curr 

    # p = self.recurse_reverse(curr.next, level + 1) 
    self.recurse_reverse(curr.next, level + 1) 

    print('-' * level, 'curr:', curr.value, '->', curr.next.value, '->', 
      curr.next.next.value if curr.next.next else curr.next.next) 

    curr.next.next = curr 
    # checking if pointer moved 
    print('-' * level, 'curr:', curr.value, '->', curr.next.value, '->', 
      curr.next.next.value if curr.next.next else curr.next.next) 
    # curr.next = None 
    # return p 

выход я получаю, когда я звоню

my_list = SinglyLinkedList() 
my_list.add_to_tail(1) 
my_list.add_to_tail(2) 
my_list.add_to_tail(3) 
my_list.add_to_tail(4) 

print(my_list._head.value) # 1 
print(my_list._head.next.value) # 2 
print(my_list._head.next.next.value) # 3 
print(my_list._head.next.next.next.value) # 4 

my_list.recurse_reverse(my_list._head, 1) 

это:

- curr: 1 | next: 2 
-- curr: 2 | next: 3 
--- curr: 3 | next: 4 
---- curr: 4 | next: None 
--- curr: 3 -> 4 -> None 
--- curr: 3 -> 4 -> 3 
-- curr: 2 -> 3 -> 4 
-- curr: 2 -> 3 -> 2 
- curr: 1 -> 2 -> 3 
- curr: 1 -> 2 -> 1 

Так печать на каждом уровне, кажется, что указатели перемещаются правильно , Однако, когда я пытаюсь напечатать голову и хвост связанного списка, я звоню recurse_reverse, я получаю 1 и 3 соответственно; все же, что я ожидал бы 4 и 1.

Во многих решениях, которые я видел, последняя строка кода curr.next = None, чтобы удалить указатель next текущего узла, но когда включите это в мой код, Я получаю AttributeError: 'NoneType' object has no attribute 'value'

Я также попытался установить

p = self.recurse_reverse(curr.next, level + 1) 

, а затем return p на последней строке, но это не работает.

Вот моя реализация:

class _LinkNode: 
    def __init__(self, value): 
     self.value = value 
     self.next = None 

class SinglyLinkedList: 
    def __init__(self): 
     self._head = None 
     self._tail = None 
     self._length = 0 

    def add_to_tail(self, value): 
     """ 
     Add a new node to the tail of the linked list. 

     Parameters 
     ---------- 
     value : int, float, string, dict, list, etc. 

     """ 
     new_node = _LinkNode(value) 

     if self._head is None: # if linked list is empty 
      self._head = new_node 

     if self._tail: # if linked list has a tail, i.e. > 1 node 
      self._tail.next = new_node 

     self._tail = new_node # regardless of current length, update tail 

     self._length += 1 

def recurse_reverse(self, curr, level): 
    # see above 

Answer 1

Есть две проблемы с вашим кодом. Сначала, если в списке содержится более одного элемента, вы не меняете _head.next, после recurse_reverse он по-прежнему будет указывать на второй элемент исходного списка, и, таким образом, последние два элемента обратного списка образуют цикл. Вторая проблема заключается в том, обменять _head и _tail в любом месте вашего кода.

Вот один из способов осуществить разворот рекурсивно:

@staticmethod 
def reverse(prev, node): 
    # Recurse until end of the list 
    if node: 
     SinglyLinkedList.reverse(node, node.next) 
     node.next = prev 

def recurse_reverse(self): 
    # Reverse nodes 
    SinglyLinkedList.reverse(None, self._head) 

    # Swap head & tail since they are reversed now 
    self._head, self._tail = self._tail, self._head