<small id='1sdGh'></small><noframes id='1sdGh'>

        <legend id='1sdGh'><style id='1sdGh'><dir id='1sdGh'><q id='1sdGh'></q></dir></style></legend>
        <i id='1sdGh'><tr id='1sdGh'><dt id='1sdGh'><q id='1sdGh'><span id='1sdGh'><b id='1sdGh'><form id='1sdGh'><ins id='1sdGh'></ins><ul id='1sdGh'></ul><sub id='1sdGh'></sub></form><legend id='1sdGh'></legend><bdo id='1sdGh'><pre id='1sdGh'><center id='1sdGh'></center></pre></bdo></b><th id='1sdGh'></th></span></q></dt></tr></i><div id='1sdGh'><tfoot id='1sdGh'></tfoot><dl id='1sdGh'><fieldset id='1sdGh'></fieldset></dl></div>

      1. <tfoot id='1sdGh'></tfoot>
          <bdo id='1sdGh'></bdo><ul id='1sdGh'></ul>
      2. 递归返回链表的中间节点

        Return middle node of linked list with recursion(递归返回链表的中间节点)
            <tbody id='BRvYb'></tbody>
        • <small id='BRvYb'></small><noframes id='BRvYb'>

                <legend id='BRvYb'><style id='BRvYb'><dir id='BRvYb'><q id='BRvYb'></q></dir></style></legend>
                <i id='BRvYb'><tr id='BRvYb'><dt id='BRvYb'><q id='BRvYb'><span id='BRvYb'><b id='BRvYb'><form id='BRvYb'><ins id='BRvYb'></ins><ul id='BRvYb'></ul><sub id='BRvYb'></sub></form><legend id='BRvYb'></legend><bdo id='BRvYb'><pre id='BRvYb'><center id='BRvYb'></center></pre></bdo></b><th id='BRvYb'></th></span></q></dt></tr></i><div id='BRvYb'><tfoot id='BRvYb'></tfoot><dl id='BRvYb'><fieldset id='BRvYb'></fieldset></dl></div>
                  <bdo id='BRvYb'></bdo><ul id='BRvYb'></ul>
                  <tfoot id='BRvYb'></tfoot>

                • 本文介绍了递归返回链表的中间节点的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着跟版网的小编来一起学习吧!

                  问题描述

                  图是由节点和边组成的非线性数据结构.节点有时也称为顶点,边是连接图中任意两个节点的线或弧.更正式的 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.

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

                  本站部分内容来源互联网,如果有图片或者内容侵犯了您的权益,请联系我们,我们会在确认后第一时间进行删除!

                  相关文档推荐

                  Initialize Multiple Numpy Arrays (Multiple Assignment) - Like MATLAB deal()(初始化多个 Numpy 数组(多重赋值) - 像 MATLAB deal())
                  How to extend Python class init(如何扩展 Python 类初始化)
                  What#39;s the difference between dict() and {}?(dict() 和 {} 有什么区别?)
                  What is a wrapper_descriptor, and why is Foo.__init__() one in this case?(什么是 wrapper_descriptor,为什么 Foo.__init__() 在这种情况下是其中之一?)
                  Initialize list with same bool value(使用相同的布尔值初始化列表)
                  setattr with kwargs, pythonic or not?(setattr 与 kwargs,pythonic 与否?)
                    <tfoot id='Vj7hx'></tfoot>
                        <bdo id='Vj7hx'></bdo><ul id='Vj7hx'></ul>

                          <small id='Vj7hx'></small><noframes id='Vj7hx'>

                            <tbody id='Vj7hx'></tbody>
                        • <i id='Vj7hx'><tr id='Vj7hx'><dt id='Vj7hx'><q id='Vj7hx'><span id='Vj7hx'><b id='Vj7hx'><form id='Vj7hx'><ins id='Vj7hx'></ins><ul id='Vj7hx'></ul><sub id='Vj7hx'></sub></form><legend id='Vj7hx'></legend><bdo id='Vj7hx'><pre id='Vj7hx'><center id='Vj7hx'></center></pre></bdo></b><th id='Vj7hx'></th></span></q></dt></tr></i><div id='Vj7hx'><tfoot id='Vj7hx'></tfoot><dl id='Vj7hx'><fieldset id='Vj7hx'></fieldset></dl></div>

                          <legend id='Vj7hx'><style id='Vj7hx'><dir id='Vj7hx'><q id='Vj7hx'></q></dir></style></legend>