python - 如何在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)

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