用递归返回链表的中间节点 [英] Return middle node of linked list with recursion

问题描述

图是由节点和边组成的非线性数据结构.节点有时也称为顶点，边缘是连接图形中任意两个节点的线或圆弧.更正式地说，图可以定义为

A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph. More formally a Graph can be defined as

推荐答案

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

Recursion is a poor choice for operating on linked lists. Almost always use a loop, which is simple to reason about, has less overhead and doesn't limit the size of the list to the call stack. It's easier to access and manipulate surrounding elements iteratively.

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

Getting the midpoint of a linked list is easy iteratively: keep two references to the head, then move one twice as fast as the other until the fast reference reaches the end of the list. The slow pointer will point to the middle node. The two-pointer technique is one of the fundamental tools for working with linked lists.

from collections import namedtuple

def middle_node(fast):
    slow = fast

    while fast and fast.next:
        fast = fast.next.next
        slow = 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

您可以使用完全相同的方法递归地进行此操作:快速引用和慢速引用.这是插入上述样板的示例:

You can do this recursively using the exact same methodology: a fast and a slow reference. Here's an example that plugs into the above boilerplate:

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

对于带有两个中间元素的奇数长度列表，这些方法总是返回一个更接近尾部的列表，但是您可以在基本情况或循环终止中添加额外的 fast.next.next 检查如果需要，有条件使中间元素更靠近头部.

For odd-length lists with two middle elements, these methods always return the one closer to the tail, but you can add an additional fast.next.next check to the base case or loop termination conditional to return the middle element closer to the head if you need.

您可以看到，递归版本在可读性或美观性方面没有任何好处，以证明其施加的额外开销和大小限制.递归更适合于非线性嵌套结构，例如数据较宽的树(这意味着调用堆栈更能够保存数据而不会溢出).树的非线性特性使得使用循环和显式堆栈来处理某些典型的遍历非常尴尬.

You can see the recursive version offers no benefits in readability or elegance to justify the added overhead and size restrictions it imposes. Recursion is better suited for nonlinear nested structures like trees where the data is wide (meaning the call stack is much more able to hold the data without overflowing). The nonlinear nature of trees makes it very awkward to use a loop and explicit stack to handle certain typical traversals.

这篇关于用递归返回链表的中间节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！