如何递归地反转单链表

Question

递归地反转节点从当前到结束的顺序。拆分当前节点及其后继节点（余数）。递归地反转后继并使其尾部指向当前节点。使当前节点指向无。

class _Node:

    def __init__(self, element, next=None):
        self._element = element
        self._next = next

    def element(self):
        return self._element

    def next(self):
        return self._next

    def set_element(self, element):
        self._element = element

    def set_next(self, next):
        self._next = next

def __init__(self, head=None):
    """Create a singly linked list that contains only head, not size"""
    self._head = head


def __str__(self):
    """Returns the string representation and the number of elements"""
    count = 0
    p = self._head
    rep = f''
    while p:
        rep += str(p.element()) + ' -> '
        p = p.next()
        count += 1
    rep += f'None: {count} element(s)'
    return rep

---

def reverse_recursively(self, current):

    if current is None:
        return current
    if current._next is None:
        return current
    successors = self.reverse_recursively(current.next())
    current._next._next = current
    current._next = None

我期望反转的输出但实际输出只是第一个节点而没有。

Answer 1

该算法确实不正确，因为它不会将self._head属性重定向到指向最后一个节点。

实际上，您不需要将参数传递给此方法。相反，当你递归到链表的末尾时，逐步移动self._head。

以下是代码的外观：

def reverse_recursively(self):
    current = self._head
    if current is None:
        return
    successor = current._next
    if successor is None:
        return
    current._next = None
    self._head = successor
    self.reverse_recursively()
    successor._next = current