def nested_list(depth):
    l = [depth]
    for i in range(depth-1, 0, -1):
        l = [i, l]
    return l

nested_list(10)

[1, [2, [3, [4, [5, [6, [7, [8, [9, [10]]]]]]]]]].

def Flatten(ul):
    fl = []
    for i in ul:
        if type(i) is list:
            fl += Flatten(i)
        else:
            fl += [i]
    return fl

Flatten(nested_list(10))

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

基准测试

l = nested_list(100)

https://stackoverflow.com/a/2158532

import collections

def flatten(l):
    for el in l:
        if isinstance(el, collections.Iterable) and not isinstance(el, (str, bytes)):
            yield from flatten(el)
        else:
            yield el

%%timeit -n 1000
list(flatten(l))

320µs±14.3µs / loop(平均±std. dev. 7次运行，每个循环1000次)

%%timeit -n 1000
Flatten(l)

60µs±10.2µs / loop(平均±std. dev. 7次运行，每个循环1000次)

list(flatten(l)) == Flatten(l)

真正的

没有装饰。只有发冷。

recursive_list_of_lists = [1,2,3,[1,2,[[3,4,[5]],7,0,1,10],100,[101,[101,[[101]],2]],0]]

k = []

def flatten(subl):
    for i in subl:
        if type(i) != type([1]):
            k.append(i)
        else:
            flatten(i)

flatten(recursive_list_of_lists)

print(k)

[1, 2, 3, 1, 2, 3, 4, 5, 7, 0, 1, 10, 100, 101, 101, 101, 2, 0]

这是一个简单的函数，它将任意深度的列表平展。不递归，避免堆栈溢出。

from copy import deepcopy

def flatten_list(nested_list):
    """Flatten an arbitrarily nested list, without recursion (to avoid
    stack overflows). Returns a new list, the original list is unchanged.

    >> list(flatten_list([1, 2, 3, [4], [], [[[[[[[[[5]]]]]]]]]]))
    [1, 2, 3, 4, 5]
    >> list(flatten_list([[1, 2], 3]))
    [1, 2, 3]

    """
    nested_list = deepcopy(nested_list)

    while nested_list:
        sublist = nested_list.pop(0)

        if isinstance(sublist, list):
            nested_list = sublist + nested_list
        else:
            yield sublist

这是另一种py2方法，我不确定它是否最快或最优雅或最安全…

from collections import Iterable
from itertools import imap, repeat, chain


def flat(seqs, ignore=(int, long, float, basestring)):
    return repeat(seqs, 1) if any(imap(isinstance, repeat(seqs), ignore)) or not isinstance(seqs, Iterable) else chain.from_iterable(imap(flat, seqs))

它可以忽略你想要的任何特定(或派生)类型，它返回一个迭代器，所以你可以将它转换为任何特定的容器，如list, tuple, dict或简单地消耗它，以减少内存占用，无论是好是坏，它可以处理初始的不可迭代对象，如int…

注意，大部分繁重的工作都是在C中完成的，因为据我所知，itertools就是这样实现的，所以虽然它是递归的，但AFAIK它不受python递归深度的限制，因为函数调用是在C中发生的，尽管这并不意味着你受到内存的限制，特别是在OS X中，它的堆栈大小有一个硬限制，直到今天(OS X Mavericks)…

有一个稍微快一点的方法，但不太便携的方法，只有在你可以假设输入的基本元素可以显式确定的情况下才使用它，否则你会得到一个无限递归，而OS X有限的堆栈大小，将抛出一个分割错误相当快……

def flat(seqs, ignore={int, long, float, str, unicode}):
    return repeat(seqs, 1) if type(seqs) in ignore or not isinstance(seqs, Iterable) else chain.from_iterable(imap(flat, seqs))

这里我们使用集合来检查类型，所以它使用O(1) vs O(类型数量)来检查是否应该忽略一个元素，当然，任何带有指定的被忽略类型的派生类型的值都会失败，这就是为什么它使用str, unicode，所以要小心使用它…

测试:

import random

def test_flat(test_size=2000):
    def increase_depth(value, depth=1):
        for func in xrange(depth):
            value = repeat(value, 1)
        return value

    def random_sub_chaining(nested_values):
        for values in nested_values:
            yield chain((values,), chain.from_iterable(imap(next, repeat(nested_values, random.randint(1, 10)))))

    expected_values = zip(xrange(test_size), imap(str, xrange(test_size)))
    nested_values = random_sub_chaining((increase_depth(value, depth) for depth, value in enumerate(expected_values)))
    assert not any(imap(cmp, chain.from_iterable(expected_values), flat(chain(((),), nested_values, ((),)))))

>>> test_flat()
>>> list(flat([[[1, 2, 3], [4, 5]], 6]))
[1, 2, 3, 4, 5, 6]
>>>  

$ uname -a
Darwin Samys-MacBook-Pro.local 13.3.0 Darwin Kernel Version 13.3.0: Tue Jun  3 21:27:35 PDT 2014; root:xnu-2422.110.17~1/RELEASE_X86_64 x86_64
$ python --version
Python 2.7.5

在尝试回答这样一个问题时，您确实需要给出作为解决方案的代码的局限性。如果它只是关于性能，我不会太介意，但作为解决方案提出的大多数代码(包括公认的答案)都不能平坦任何深度大于1000的列表。

当我说大多数代码时，我指的是所有使用任何形式递归的代码(或调用递归的标准库函数)。所有这些代码都失败了，因为每次递归调用，(调用)堆栈都会增加一个单元，(默认)python调用堆栈的大小为1000。

如果您对调用堆栈不太熟悉，那么下面的内容可能会有所帮助(否则您可以直接滚动到Implementation)。

调用堆栈大小和递归编程(地下城类比)

找到宝藏和出口

想象一下，你进入一个有编号房间的巨大地牢，寻找宝藏。你不知道那个地方，但你对如何找到宝藏有一些暗示。每个指示都是一个谜(难度不同，但你无法预测它们有多难)。你决定考虑一个节省时间的策略，你做了两个观察:

找到宝藏很难(很长时间)，因为你必须解决(可能很难的)谜语才能到达那里。 一旦找到宝藏，回到入口可能很容易，你只需要在另一个方向使用相同的路径(尽管这需要一点记忆来回忆你的路径)。

当你进入地下城时，你会注意到这里有一个小笔记本。你决定用它来写下你在解开谜语后(当进入一个新房间时)离开的每个房间，这样你就可以回到入口。这是一个天才的想法，你甚至不会花一分钱来实施你的策略。

你进入地下城，成功地解决了前1001个谜语，但你没有计划的事情出现了，你借来的笔记本没有空间了。你决定放弃你的任务，因为你宁愿没有宝藏也不愿永远迷失在地牢里(这看起来确实很聪明)。

执行递归程序

基本上，这和找到宝藏是一样的。地牢是计算机的内存，你现在的目标不是找到宝藏，而是计算某个函数(为给定的x找到f(x))。指示只是帮助你求解f(x)的子例程。你的策略与调用堆栈策略相同，notebook是堆栈，rooms是函数的返回地址:

x = ["over here", "am", "I"]
y = sorted(x) # You're about to enter a room named `sorted`, note down the current room address here so you can return back: 0x4004f4 (that room address looks weird)
# Seems like you went back from your quest using the return address 0x4004f4
# Let's see what you've collected 
print(' '.join(y))

The problem you encountered in the dungeon will be the same here, the call stack has a finite size (here 1000) and therefore, if you enter too many functions without returning back then you'll fill the call stack and have an error that look like "Dear adventurer, I'm very sorry but your notebook is full": RecursionError: maximum recursion depth exceeded. Note that you don't need recursion to fill the call stack, but it's very unlikely that a non-recursive program call 1000 functions without ever returning. It's important to also understand that once you returned from a function, the call stack is freed from the address used (hence the name "stack", return address are pushed in before entering a function and pulled out when returning). In the special case of a simple recursion (a function f that call itself once -- over and over --) you will enter f over and over until the computation is finished (until the treasure is found) and return from f until you go back to the place where you called f in the first place. The call stack will never be freed from anything until the end where it will be freed from all return addresses one after the other.

如何避免这个问题?

这其实很简单:“如果你不知道递归有多深，就不要使用递归”。这并不总是正确的，因为在某些情况下，尾部调用递归可以被优化(TCO)。但在python中，情况并非如此，即使“写得很好”的递归函数也不会优化堆栈的使用。Guido有一篇关于这个问题的有趣文章:尾递归消除。

有一种技术可以让任何递归函数迭代，这种技术我们可以叫它，带上你自己的笔记本。例如，在我们的特定情况下，我们只是在探索一个列表，进入一个房间相当于进入一个子列表，你应该问自己的问题是，我如何从一个列表返回到它的父列表?答案并不复杂，重复以下步骤直到栈空:

当输入新的子列表时，将当前列表地址和索引推入堆栈(注意，列表地址+索引也是一个地址，因此我们只是使用与调用堆栈使用的完全相同的技术); 每次找到一个项目，交出它(或将它们添加到列表中); 一旦一个列表被完全浏览，使用堆栈返回地址(和索引)返回到父列表。

还要注意，这等价于树中的DFS，其中有些节点是子列表a =[1,2]，有些是简单的项:0、1、2、3、4(对于L =[0，[1,2]， 3,4])。这棵树是这样的:

                    L
                    |
           -------------------
           |     |     |     |
           0   --A--   3     4
               |   |
               1   2

DFS遍历的预顺序为:L, 0, A, 1, 2, 3, 4。记住，为了实现迭代的DFS，您还“需要”一个堆栈。我之前提出的实现会产生以下状态(对于堆栈和flat_list):

init.:  stack=[(L, 0)]
**0**:  stack=[(L, 0)],         flat_list=[0]
**A**:  stack=[(L, 1), (A, 0)], flat_list=[0]
**1**:  stack=[(L, 1), (A, 0)], flat_list=[0, 1]
**2**:  stack=[(L, 1), (A, 1)], flat_list=[0, 1, 2]
**3**:  stack=[(L, 2)],         flat_list=[0, 1, 2, 3]
**3**:  stack=[(L, 3)],         flat_list=[0, 1, 2, 3, 4]
return: stack=[],               flat_list=[0, 1, 2, 3, 4]

在这个例子中，堆栈的最大大小是2，因为输入列表(因此树)的深度是2。

实现

在python中，你可以通过使用迭代器而不是简单的列表来简化实现。对(sub)迭代器的引用将用于存储子列表的返回地址(而不是同时拥有列表地址和索引)。这不是很大的区别，但我觉得这样更有可读性(也更快一点):

def flatten(iterable):
    return list(items_from(iterable))

def items_from(iterable):
    cursor_stack = [iter(iterable)]
    while cursor_stack:
        sub_iterable = cursor_stack[-1]
        try:
            item = next(sub_iterable)
        except StopIteration:   # post-order
            cursor_stack.pop()
            continue
        if is_list_like(item):  # pre-order
            cursor_stack.append(iter(item))
        elif item is not None:
            yield item          # in-order

def is_list_like(item):
    return isinstance(item, list)

另外，请注意在is_list_like中我有isinstance(item, list)，它可以被更改为处理更多的输入类型，这里我只想有一个最简单的版本，其中(iterable)只是一个列表。但你也可以这样做:

def is_list_like(item):
    try:
        iter(item)
        return not isinstance(item, str)  # strings are not lists (hmm...) 
    except TypeError:
        return False

这将字符串视为“简单项”，因此平坦iter([["test"， "a"]， "b])将返回["test"， "a"， "b"]，而不是["t"， "e"， "s"， "t"， "a"， "b"]。注意，在这种情况下，iter(item)在每个项目上调用两次，让我们假设这是读者的一个练习，以使其更清晰。

对其他实现的测试和备注

最后，请记住，您不能使用print(L)打印无限嵌套列表L，因为在内部它将使用对__repr__的递归调用(RecursionError:在获取对象的repr时超过最大递归深度)。出于同样的原因，涉及str的flatten解决方案将失败，并显示相同的错误消息。

如果你需要测试你的解决方案，你可以使用这个函数来生成一个简单的嵌套列表:

def build_deep_list(depth):
    """Returns a list of the form $l_{depth} = [depth-1, l_{depth-1}]$
    with $depth > 1$ and $l_0 = [0]$.
    """
    sub_list = [0]
    for d in range(1, depth):
        sub_list = [d, sub_list]
    return sub_list

使:build_deep_list(5) > > >[4,[3,(2,[1,[0]]]]]。

我们也可以使用python的'type'函数。当迭代列表时，我们检查项是否为列表。如果不是，我们“追加”它，否则我们“扩展”它。这里是一个示例代码-

l=[1,2,[3,4],5,[6,7,8]]
x=[]
for i in l:
    if type(i) is list:
        x.extend(i)
    else:
        x.append(i)
print x

输出:

[1, 2, 3, 4, 5, 6, 7, 8]

要了解更多关于append()和extend()的信息，请访问这个网站: https://docs.python.org/2/tutorial/datastructures.html