使用递归返回链表的中间

Question

def find_mid(self, node, ret_count, ):
    if node.next == None:
        self.len += 1
        return

    else:
        self.len += 1
        self.find_mid(node.next, ret_count + 1)


    if ret_count == int((self.len - 1)/2):
        print(node)                      # this node should be returned by the function
        print(node.data)

我试图在不知道链表长度的情况下找到它的中间位置。如果我只打印结果，它可以工作，但是我想返回它，所以我可以写：

middleNode = LinkedList.find_mid(head, 0)         

每次尝试时，该函数只会返回废话或给我一个错误。有没有办法在这种递归中返回像这样的值？

PS：我知道我可以将函数分为两部分，但是我认为这样做会比较慢，而且这个问题更多的是关于从递归返回的问题，而不仅仅是找到链表的中间部分。

Answer 1

之所以会打印正确的值，但将打印更改为return语句不起作用，是因为您没有在基本情况下返回该节点。因此，当您找到中点并返回该节点时，上一个节点将不返回任何内容或利用递归步骤的结果。这是一个修改，它将利用您的递归步骤的结果并将其返回到调用链中。

我不完全相信您的中点计算在每种情况下都是正确的（3个节点的情况将返回节点1而不是节点2），所以我做了一点修改。

def find_mid(self, node, ret_count, ):
    if node.next == None:
        self.len += 1
        return None
    else:
        self.len += 1
        # return_node will either be the midpoint if we have found it, or None if we are still searching
        return_node = self.find_mid(node.next, ret_count + 1)

        # We have found the midpoint no need to check ret_count anymore
        if return_node:
            return return_node

    # If we make it here we have not found the midpoint node but have counted the total number of Nodes.
    # Set midpoint assuming an even number of nodes
    midpoint = int(self.len/2)
    # If odd number of nodes set midpoint accordingly
    if self.len % 2 != 0:
        midpoint = int((self.len+1)/2)

    # Check if the current node is the midpoint (len = 3 or len = 4 results in node 2 being midpoint
    if ret_count == midpoint:
        # Return the node
        return node
    else:
        # Potentially not necessary but will ensure that non-midpoint recursive steps return None
        return None

Answer 2

对于在链表上进行操作，递归是一个糟糕的选择。几乎总是使用循环，这种循环的原因很简单，开销较小，并且不会限制调用堆栈的列表大小。迭代访问和操作周围的元素更容易。

获得链接列表的中点很容易迭代：将两个引用保持在头部，然后将另一个引用移动两倍，直到快速引用到达列表的末尾。慢速指针将指向中间节点。两指针技术是处理链表的基本工具之一。

您可以使用完全相同的方法递归执行此操作：快速引用和慢速引用。

这里是一个例子：

from collections import namedtuple

def middle_node(fast, slow=None):
    if not slow:
        slow = fast

    if fast and fast.next:
        return middle_node(fast.next.next, slow.next)

    return slow

if __name__ == "__main__":
    Node = namedtuple("Node", "val next")
    odd = Node(0, Node(1, Node(2, Node(3, Node(4, None)))))
    even = Node(0, Node(1, Node(2, Node(3, Node(4, Node(5, None))))))
    print(middle_node(odd).val) # => 2
    print(middle_node(even).val) # => 3

对于具有两个中间元素的奇数长度列表，这总是返回一个更靠近尾部的元素，但是您可以在基本情况下添加附加的fast.next.next检查，如果需要，可以使中间元素更靠近头部。