递归返回单链表的子列表

Question

我试图递归返回单链表的子列表。

例：列表=3-

sub（list，1,2）应返回4-

参数1-开始索引

参数2-子列表的长度

我有点麻烦，因为我的代码只返回子列表的最后一个元素，而不是整个子列表。

def sub(list, start, length) -> Node:
    if list is None:
        return None
    elif start <= 0:
        if length ==1:
            list.next = None
            return list
        else:
            return sub(list.next, start - 1, length - 1)
    else:

        return sub(list.next, start - 1, length)

Answer 1

在遍历主结构时，可以在sub函数中使用一个参数来存储累积的子列表：

def sub(lst, s, e, c = 0, new_l = None):
   if c >= e:
      return new_l
   if lst is None:
      raise IndexError('index out of bounds')
   return sub(lst.next, s, e, c = c+1, new_l = None if c + 1 <= s else getattr(new_l, 'add_node', Lst)(lst.value))

Lst实施：

class Lst:
   def __init__(self, val=None):
      self.value, self.next = val, None
   def add_node(self, val):
      if self.value is None:
         self.value = val
      elif self.next is None:
         self.next = Lst(val)
      else:
         self.next.add_node(val)
      return self
   def __repr__(self):
      return f'{self.value}{"" if self.next is None else " -> "+repr(self.next)}'


l = Lst()
for i in range(10):
   l.add_node(i)

print(sub(l, 0, 4))
print(sub(l, 2, 7))
print(sub(l, 5, 12))

输出：

0 -> 1 -> 2 -> 3
2 -> 3 -> 4 -> 5 -> 6
  File "<stdin>", line 6, in sub
  [Previous line repeated 7 more times]
File "<stdin>", line 5, in sub
IndexError: index out of bounds