递归返回链表的中间节点
问题描述
图是由节点和边组成的非线性数据结构.节点有时也称为顶点，边是连接图中任意两个节点的线或弧.更正式的 Graph 可以定义为
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.
相关文章