使用递归返回链表的中间节点

Question

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

Answer 1

在操作链表时，递归不是一个好的选择。几乎总是使用循环，这很容易理解，具有较少的开销，并且不会限制调用堆栈的列表大小。它更容易迭代地访问和操作周围的元素。

通过迭代获得链表的中点很容易:保留两个指向头部的引用，然后移动其中一个的速度是另一个的两倍，直到快速引用到达列表的末尾。慢速指针将指向中间节点。双指针技术是使用链表的基本工具之一。

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检查，以返回更靠近头部的中间元素。

您可以看到，递归版本在可读性或优雅方面没有提供任何好处，以证明它所施加的额外开销和大小限制是合理的。递归更适合于像树这样的非线性嵌套结构，在这种结构中数据很宽(这意味着调用堆栈能够更好地保存数据而不会溢出)。树的非线性特性使得使用循环和显式堆栈来处理某些典型的遍历非常笨拙。

Answer 2

这会打印出正确的值，但将print更改为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 3

递归是处理链表的一个很好的选择，因为链表是递归数据结构。递归允许我们的程序的结构与我们的数据结构相匹配

# 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