使用递归以反向顺序返回节点类的字符串表示形式

Question

我有一个类节点：

class LinkedNode:
    __slots__ = 'val', 'next'
    def __init__(self, val, next):
        self.val = val  # element at the node
        self.next = next  # next node reference

    def __str__(self):
        return str(self.val)

    __repr__ = __str__

我试图以相反的顺序返回节点列表的字符串表示，但使用递归。它不会修改节点，而只返回节点的字符串表示形式。我也想要正确格式化。

所以如果节点是：

{1, 2, 3}

我想使用递归函数，以便它可以打印：

3, 2, 1

我有以下功能：

def reverse_str(node):
    str_rep = ""
    if node is None:
        return str_rep
    else:
        str_rep = str(node.val)
        # For str(node.val), there is a class function that returns 
        # str(self.val)
        str_rep = reverse_str(node.next) + str_rep + ", "

如果节点是：

{1, 2, 3}

我的结果是：

3, 2, 1, # Trailing comma

我似乎无法找到一种方法来消除尾随逗号，同时保持函数是递归的。这可能是一个简单的if / else语句，但我不知道要测试什么来查看这是否是第一个头节点。我也不想修改Node类。

任何建议或想法都会有所帮助！谢谢。

Answer 1

可能你需要','.join(a, b)，但代码的更深层问题在于其他地方，请参阅注释。

基本上，你正在试图找出一个链，但是python对于保持指针来说并不是太好了，而不是C。除非你必须使用一个类，否则请考虑你的数据结构是一个字典列表。

Answer 2

您可以创建一个充当“帮助器”的属性来生成节点列表，然后使用__str__方法返回一个字符串：

class _List:
  def __init__(self, _val=None):
    self.val, self._next = _val, None
  def insert_val(self, _val):
    if self.val is None:
      self.val = _val
    else:
      getattr(self._next, 'insert_val', lambda x:setattr(self, '_next', _List(x)))(_val)
  @property
  def to_list(self):
    return [self.val, *getattr(self._next, 'to_list', [])]
  def __str__(self):
    return ', '.join(list(map(str, self.to_list))[::-1])

l = _List()
for i in range(10):
  l.insert_val(i)

print(l)

输出：

9, 8, 7, 6, 5, 4, 3, 2, 1, 0

Answer 3

您需要检查节点为None的情况（即前一个节点是最后一个节点）并以不同方式处理该情况，例如：

def reverse_str(node):
    if node is None:
        return None
    else:
        str_rep = str(node.val)
        # For str(node.val), there is a class function that returns
        # str(self.val)
        s = reverse_str(node.next)
        str_rep = s + ", " + str_rep if s else str_rep
        return str_rep

three = LinkedNode(3, None)
two = LinkedNode(2, three)
one = LinkedNode(1, two)

print(reverse_str(one))

产量

3, 2, 1