如何在Python中一次遍历链表中找到中间元素？

Question

我正试图解决一个链表问题，使用Python在单次遍历中找到中间元素。请问有人能够检查我的代码并提供最佳方法吗？

  class Node(object):
      def __init__(self, data=None, next=None):
          self.data = data
          self.next = next
      def __str__(self):
          return str(self.data)

  def print_nodes(node):
      while node:
          print node
          node = node.next

  def find_middle(node):
      while node:
          current = node
          node = node.next
          second_pointer = node.next
          next_pointer = second_pointer.next
          if next_pointer is None:
              return "Middle node is %s" % str(current)

  node1 = Node(1)
  node2 = Node(2)
  node3 = Node(3)
  node4 = Node(4)
  node5 = Node(5)

  node1.next = node2
  node2.next = node3
  node3.next = node4
  node4.next = node5

  print find_middle(node1)

- James Sapam

---

当你有这样的松散节点时，你可能也要小心 - 如果我放入一个循环（node1.next = node1），那么大多数find_middle函数将进入无限循环。像链表这样的包装结构可能会帮助你解决问题。 - en_Knight

不要将他人的解决方案编辑到你的问题代码中。这会使后来者难以理解问题。 - user2357112

好的，我会恢复回我的旧版本。 - James Sapam

递归允许吗？ - Travis Griggs

是的，请提出任何建议，非常欢迎。 - James Sapam

Answer 1

我已经为您合并了所有的方法，包括创建、查找和打印。

class Node(object):
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next
    def __str__(self):
        return str(self.data)

def create_linked_list(n):
    """Creating linked list for the given
       size"""
    linked_list = Node(1)
    head = linked_list
    for i in range(2, n):
        head.next = Node(i)
        head = head.next
    return linked_list

def print_linked_list(node):
    """To print the linked list in forward"""
    while node:
        print '[',node,']','[ref] ->',
        node = node.next
    print '-> None'

def find_middle1(node):
    tick = False
    half = node
    while node:
        node = node.next
        if tick:
            half = half.next
        tick = not tick
    return "Middle node is %s" % str(half)

def find_middle2(node):
    list = []
    while node:
        list.append(node)
        node = node.next
    return "Middle node is %s" % str(list[len(list)/2])


node = create_linked_list(10)
print_linked_list(node)

print find_middle1(node)
print find_middle2(node)

输出：

[ 1 ] [ref] -> [ 2 ] [ref] -> [ 3 ] [ref] -> [ 4 ] [ref] -> [ 5 ] [ref] -> [ 6 ] [ref] -> [ 7 ] [ref] -> [ 8 ] [ref] -> [ 9 ] [ref] -> -> None
Middle node is 5
Middle node is 5

- user3058156

---

对于你的 find_middle2 方法，你应该使用 len(list)//2 将任何浮点数转换为整数。 - Adnan

@Adnanshah：他正在使用Python2，因此11 / 2是地板除法，结果为5。https://dev59.com/JXVC5IYBdhLWcg3wykaj 此外，应避免使用list = []作为列表变量名。 - aspiring1

Answer 2

这里有一种方式，它只需要一遍操作，但可能不像您想的那样高效：

def find_middle(node):
    list = []
    while node:
        list.append(node)
        node = node.next
    return list[len(list)/2]

这个能行吗？

- en_Knight

---

嗯，这是另一种有趣的方法，而不使用双指针算法。我会等待更多建议。非常感谢您的答案和建议。 - James Sapam

没问题。你的算法似乎不起作用 - 它总是返回列表中的倒数第三个元素，我认为不是中间元素。双指针是一个好主意，但它需要在你的链表中进行相当多的簿记工作。你尝试过这种实现方式吗？ - en_Knight

让我再检查一下，你能否编辑我的代码？ - James Sapam

也许吧，但请考虑你的代码在做什么——它将一个指针提前了一个位置，并将另一个指针提前了两个位置。当向前两个指针时为空时，它就会停止，并返回当前指针；显然，它将返回离结尾还有两个节点的那个节点。这样说你明白了吗？ - en_Knight

Answer 3

你可以保留两个指针，其中一个移动速度是另外一个的一半。

def find_middle(node):
    tick = False
    half = node
    while node:
        node = node.next
        if (tick):
            half = half.next
        tick = not tick
    return "Middle node is %s" % str(half)

- Jordan P

---

原始文本中有一些错误。这似乎在python3中对我有效：http://pastebin.com/2vtaPHRq - Jordan P

嗨Jordan，现在它已经工作了，在更改tick = not tick之后，现在我想问你这个逻辑，我并没有很清楚地理解它是如何找到一半的。 - James Sapam

half = half.next 在每两次 node = node.next 调用一次。当 node 到达列表末尾时，half 将在列表的一半位置。 - Jordan P

这是OP真正寻找的吗？在我看来，这基本上是一种半版本的传递，只是同时完成。 - Travis Griggs

不错的调用。根据数组的大小和优化级别（如果half.next导致缓存未命中），这可能会产生0（1.5n）的运行时间。 - Jordan P

Answer 4

寻找链表中间元素的伪代码：

fast = head
slow = head


while(fast!=null) {



 if(fast.next!=null) {

      fast = fast.next.next
      slow = slow.next
 }

 else { 

  break
 }
}

// middle element
return slow

- Vikram Bhat

Answer 5

以上所有答案都是正确的，但对我来说，以下方法最好：

        def middleNode(self, head: ListNode) -> ListNode:
            list=[]
            while head:
                list.append(head)
                head=head.next
            return list[floor(len(list)/2)]

在这里，使用 floor 函数帮助我避免了错误，否则我的代码会出错。

- Areeha

Answer 6

找到链表的中间节点最好的方法是使用两个指针：

 P1 = root
    P2 = root
    While not p2.next == Null:
    P1 =p1.next
    P2 =P2.next.next

- user7983445

Answer 7

//Linked list

ll = {'A': ["data", "B"],
 'B': ["data", "C"],
 'C': ["data", "D"],
 'D': ["data", "E"],
 'E': ["data", None]}


def find_next_node(node="A"):
    return ll[node][1] if ll[node][1] else None

def find_mid_node(head="A"):
    slow = head
    fast = head
    while(fast!=None):
        for i in range(2):
            if find_next_node(fast):
                fast = find_next_node(node=fast)
            else:
                return slow

        for j in range(1):
            slow = find_next_node(node=slow)


print (find_mid_node())

- anushjay

Answer 8

这与James和Jordan已经发布的内容非常相似，只是在它所做的事情方面更简单，并且我已经添加了解释来作为注释说明它的实际功能

class Node:
  def __init__(self, data=None, next=None):
    self.data = data
    self.next = next 
# loop through the items and check for next items using two pointers (fast and slow)
# set the speed for fast twice higher than the slow pointer so when when fast reaches
# the end the slow would be in the middle
def find_middle(head ):
    fast = slow = head 
    #slow = head
    while fast.next != None and fast.next.next != None:
        fast = fast.next.next
        slow = slow.next

    # slow is now at the middle :)
    print (slow.data  )


#setup data
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

find_middle(node1)

- grepit

Answer 9

好的，这不是一个好主意。但它确实满足只遍历一次的约束条件。它利用堆栈来模拟半遍历（向后而不是向前），而不是只遍历一次（和次要的半遍历）。这不是一个好主意，因为Python没有无限可扩展的堆栈（我希望Python能从Smalltalk的人们那里学到一些东西），所以你真的只能处理数百个列表，绝对不能处理数千个（顺便说一下，这是Python3）。

首先，我修改了您的脚本，以更改值并构建更大的列表：

last = root = Node(1)
for i in range(2, 312):
    node = Node(i)
    last.next = node
    last = node

由于我们正在使用堆栈和递归，因此我们需要一种方法来突然返回到深层调用堆栈之外。因此，我们创建了一个异常子类，它实际上更像是一种“通知”而不是“异常”。

class FoundMiddleNode(Exception):
    def __init__(self, node):
        super().__init__()
        self.node = node

现在是递归函数：

def probeForMiddle(node, length):
    if node.next is None: #recursion stopper
        return length
    #call recursively
    lengthToEnd = probeForMiddle(node.next, length + 1)
    #is my distance from start half of what is being returned recursively as the full length?
    if (lengthToEnd // 2) - length == 0: 
        raise FoundMiddleNode(node) #throw an exception to abort the rest of the stack walk
    return lengthToEnd

我们使用它的方式如下：

try:
    probeForMiddle(root, 0)
except FoundMiddleNode as e:
    print(e.node)

不太美观，对于任何接近生产代码的东西都不是一个好主意。但它是一个（滥用）递归和异常来填充只遍历一次要求的不错例子。

- Travis Griggs

Answer 10

你可以编写更简短的代码来查找中间节点。以下是代码片段：

   def find_middle(node):
      half = node
      while node and node.next is not None:
         node = node.next.next
         half = half.next
      return half

几个重要的注意事项:

1. 逻辑保持不变，即保持两个指针，一个快速指针，另一个慢速指针。
2. 编写一个链表类来创建一个链表，使用循环而不是显式设置下一个指针。

- Shagun Pruthi