给定一个非环的单向链表，寻找该链表的中间元素
可以通过两个指针同时遍历的方式，一个前进一步，一个前进两步，最后慢的指针所指位置为链表中间元素
# coding: utf-8
# @author zhenzong
# @date 2018-05-20 13:24
class Node(object):
def __init__(self, value, next_node):
self.value = value
self.next_node = next_node
def __str__(self):
return str(self.value)
__repr__ = __str__
def mid_list(head):
if not head:
return None
slow, fast = head, head
while fast.next_node and fast.next_node.next_node:
fast = fast.next_node.next_node
slow = slow.next_node
return slow
def list_to_str(_node):
if not _node:
return ''
ret = str(_node)
tmp = _node.next_node
while tmp:
ret = '%s,%s' % (ret, tmp)
tmp = tmp.next_node
return ret
def test(length_array):
for length in length_array:
node = None
for i in range(length, 0, -1):
node = Node(i, node)
print 'length: %s, list: %s, mid: %s' % (length, list_to_str(node), mid_list(node))
test([1, 2, 3, 10, 11, 12])
# 输出
# length: 1, list: 1, mid: 1
# length: 2, list: 1,2, mid: 1
# length: 3, list: 1,2,3, mid: 2
# length: 10, list: 1,2,3,4,5,6,7,8,9,10, mid: 5
# length: 11, list: 1,2,3,4,5,6,7,8,9,10,11, mid: 6
# length: 12, list: 1,2,3,4,5,6,7,8,9,10,11,12, mid: 6
