給定一個(gè)非環(huán)的單向鏈表，尋找該鏈表的中間元素

可以通過(guò)兩個(gè)指針同時(shí)遍歷的方式，一個(gè)前進(jìn)一步，一個(gè)前進(jìn)兩步，最后慢的指針?biāo)肝恢脼殒湵碇虚g元素

# 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