List Flatten

[bearophile]

This is my first Python program (it's an improvement of a recursive
version by Luther Blissett). Given a list like this:
[["a", 2, [], [3, 5, (2,1), [4]]]]

It produces the "flatted" version:
["a", 2, 3, 5, (2, 1), 4]

I think this operation is quite important, and it's similar to the
built-in Mathematica Flatten function:
l = {{"a", 2, {}, {3, 5, {4}}}}
Flatten[l]
=> {"a", 2, 3, 5, 4}

This program works for very deep lists too, without giving Stack
overflow like the recursive version (and it's faster than the
recursive version).

There's an added loop to speed up the already quite flat lists (I
think they are the most common) but this slows down a bit the
flattening of very deep lists. I don't know if this is the best
compromise for average situations.
I've tried a version with the stack as a dictionary, but the timings
are almost the same and it uses a LOT more memory (I've tried it with
lists with a million nested levels).

def listflatten(l):
    """Flattens a list, examples:
    listflatten("a") => "a"
    listflatten([]) => []
    listflatten([[1,[2,[],"a"]]) => [1,2,"a"]
    """
    if type(l) != list:
        return l
    else:
        result = []
        stack = []
        stack.append((l,0))
        while len(stack) != 0:
            sequence, j = stack.pop(-1)
            while j < len(sequence):
                if type(sequence[j]) != list:
                    k, j, lens = j, j+1, len(sequence)
                    while j < len(sequence) and \
                          (type(sequence[j]) != list):
                        j += 1
                    result.extend(sequence[k:j])
                else:
                    stack.append((sequence, j+1))
                    sequence, j = sequence[j], 0
        return result

I think this program is essentially (almost) O(n) because the sequence
list isn't really copied when it's inserted into the stack, and in
some tests I've seen that the pushes-pops in the lists tail are almost
O(1) (but the Append of an element in the head of a list is ~O(n)).
Bugs: for really big lists this program can crash for memory overflow.
I still don't know how to fix this problem. The exception MemoryError
doesn't come even when the HD trashes a lot... This is probably a
memory management problem of the Operative System... -_-

Comments are appreciated,
bear hugs,
bearophile