图是由节点和边组成的非线性数据结构。节点有时也称为顶点，边是连接图形中任意两个节点的直线或弧。更正式的图可以定义为
递归对于在链表上操作来说是一个糟糕的选择。几乎总是使用循环，这很容易推理，开销更少，并且不会将列表的大小限制为调用堆栈。以迭代方式访问和操作周围元素更容易。
迭代获取链表的中点很容易：保留对头部的两个引用，然后移动一个比另一个快两倍，直到快速引用到达列表的末尾。慢指针将指向中间节点。双指针技术是处理链表的基本工具之一。
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
您可以使用完全相同的方法递归执行此操作：快速和慢速引用。下面是一个插入上述样板的示例：
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检查，以返回更靠近头部的中间元素。
您可以看到递归版本在可读性或优雅性方面没有任何好处，以证明它施加的额外开销和大小限制是合理的。递归更适合非线性嵌套结构，如数据较宽的树(这意味着调用堆栈更能够保存数据而不会溢出(。树的非线性特性使得使用循环和显式堆栈来处理某些典型的遍历变得非常尴尬。
这打印了正确的值，但将打印更改为 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
递归是处理链表的绝佳选择，因为链表是递归数据结构。递归允许我们的程序结构与数据结构相匹配 -
# linked_list.py
empty = None
class node:
def __init__(self, value, next = None):
self.value = value
self.next = next
def to_str(t = empty):
if not t:
return "None"
else:
return f"{t.value} -> {to_str(t.next)}"
def middle(t = empty):
def loop(t, ff):
if not t:
return None
elif ff and ff.next:
return loop(t.next, ff.next.next)
else:
return t.value
return loop(t, t)
让我们从基本构建块中获得一些输出 -
# main.py
from linked_list import node, to_str, middle
t1 = node(1, node(2, node(3)))
t2 = node(1, node(2, node(3, node(4))))
t3 = node(1, node(2, node(3, node(4, node(5)))))
print(to_str(t1)) # 1 -> 2 -> 3 -> None
print(to_str(t2)) # 1 -> 2 -> 3 -> 4 -> None
print(to_str(t3)) # 1 -> 2 -> 3 -> 4 -> 5 -> None
print(middle(t1)) # => 2
print(middle(t2)) # => 3
print(middle(t3)) # => 3
将功能模块包装在一个class中会让它感觉更pythonic -
# linked_list.py
empty = # ...
class node # ...
def to_str # ...
def middle # ...
def from_list(l = []):
if not l:
return empty
else:
return node(l[0], from_list(l[1:]))
class linked_list:
def __init__(self, root = None):
self.root = root
def __str__(self):
return to_str(self.root)
def middle(self):
return middle(self.root)
def from_list(l = []):
return linked_list(from_list(l))
现在，我们获得了函数式模块的所有好处，并具有oop式界面的便利性 -
from linked_list import linked_list
t1 = linked_list.from_list([1, 2, 3])
t2 = linked_list.from_list([1, 2, 3, 4])
t3 = linked_list.from_list([1, 2, 3, 4, 5])
print(t1) # 1 -> 2 -> 3 -> None
print(t2) # 1 -> 2 -> 3 -> 4 -> None
print(t3) # 1 -> 2 -> 3 -> 4 -> 5 -> None
print(t1.middle()) # => 2
print(t2.middle()) # => 3
print(t3.middle()) # => 3