递归插入链表中的节点，给定位置和值

问题描述

我正在实现一个仅包含值的链表，并尝试利用递归遍历该列表以在列表中的特定位置插入特定值。我已经解决了如何使用WHILE循环来完成此任务，但是，在将其转换为递归函数时遇到问题。

insert方法包含值和索引作为参数，如果位置为0，则函数会将头节点设置为新值。否则，我创建一个设置为节点头部的new_node变量，当位置大于1时，new_node设置为下一个节点，index减1。我可以使用此方法插入，但无法使用递归实现此操作。

我的迭代解决方案

class Node:
    def __init__(self, data, node=None):
        self._data = data
        self._next = node

    def get_next(self):
        return self._next

    def get_data(self):
        return self._data

    def set_next_node(self, val):
        self._next = val 


class LinkedList:
    def __init__(self):
        self._head = None

    def get_head(self):
        return self._head

    def set_head(self, value):
        self._head = value

    def insert(self, value, index):
        if index == 0:
            self._head = Node(value, self._head)
            return
        new_node = self._head
        while index > 1:
            new_node = new_node.get_next()
            index -= 1
        new_node._next = Node(value, new_node.get_next()) 

---

解决方案

Node和LinkedList需要单独的类吗？否则，您可以按如下方式简化代码：

class Node:
    def __init__(self, data, node=None):
        self.data = data
        self.next = node
    def __repr__(self):
        return f"{self.data}, {self.next}" if self.next else str(self.data)
    def insert(self, value, index=0):
        if self.next:
            if index == 0:
                self.next, self.data = Node(self.data, self.next), value
            else:
                self.next.insert(value, index - 1)
        else: # if terminal node, ignore index
            self.next = Node(value)

ll = Node(1, Node(3, Node(4)))
print(ll) # 1, 3, 4
ll.insert(2, 1)
print(ll) # 1, 2, 3, 4
ll.insert(5, 4)
print(ll) # 1, 2, 3, 4, 5

基本上，每个Node本身代表一个从该节点开始的链表，我相信这符合递归性的概念。

这里，insert只有在index == 0时才做真正的工作，这与迭代解决方案中的想法相同。否则(如果index > 0)，它会将作业抛给索引少一个的下一个节点(self.next.insert(value, index - 1))。

---

如果您必须维护Node-LinkedList结构，可以执行以下操作：

class Node:
    def __init__(self, data, node=None):
        self.data = data
        self.next = node

class LinkedList:
    def __init__(self, node=None):
        self.head = node
    def __repr__(self):
        values = []
        curr = self.head
        while curr:
            values.append(curr.data)
            curr = curr.next
        return ', '.join(map(str, values))
    def insert(self, value, index=0, node=None):
        node = node or self.head # if node==None, then assign self.head
        if node.next:
            if index == 0:
                node.next, node.data = Node(node.data, node.next), value
            else:
                self.insert(value, index=index-1, node=node.next)
        else: # if terminal node, ignore index
            node.next = Node(value)

ll = LinkedList(Node(1, Node(3, Node(4))))
print(ll) # 1, 3, 4
ll.insert(2, 1)
print(ll) # 1, 2, 3, 4
ll.insert(5, 4)
print(ll) # 1, 2, 3, 4, 5

请注意，insert还有一个状态变量node。虽然在技术上是递归的，但我对它的美观持保留态度。