Lintcode 22. Flatten List

Given a list, each element in the list can be a list or integer. flatten it into a simply list with integers.

Example

Example 1:
 Input:  [[1,1],2,[1,1]]
 Output: [1,1,2,1,1]
 
 Explanation:
 flatten it into a simply list with integers.

Example 2:
 Input:  [1,2,[1,2]]
 Output:[1,2,1,2]
 
 Explanation:  
 flatten it into a simply list with integers.

Example 3:
 Input: [4,[3,[2,[1]]]]
 Output:[4,3,2,1]
 
 Explanation: 
 flatten it into a simply list with integers.

Challenge

Do it in non-recursive.

Notice

If the element in the given list is a list, it can contain list too.

Code (Java):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77

/**  * // This is the interface that allows for creating nested lists.  * // You should not implement it, or speculate about its implementation  * public interface NestedInteger {  *  *     // @return true if this NestedInteger holds a single integer,  *     // rather than a nested list.  *     public boolean isInteger();  *  *     // @return the single integer that this NestedInteger holds,  *     // if it holds a single integer  *     // Return null if this NestedInteger holds a nested list  *     public Integer getInteger();  *  *     // @return the nested list that this NestedInteger holds,  *     // if it holds a nested list  *     // Return null if this NestedInteger holds a single integer  *     public List<NestedInteger> getList();  * }  */ import java.util.Iterator;   public class Solution {       // @param nestedList a list of NestedInteger     // @return a list of integer     public List<Integer> flatten(List<NestedInteger> nestedList) {         // Write your code here         NestedIntegerIterator it = new NestedIntegerIterator(nestedList);                   List<Integer> ans = new ArrayList<>();         while (it.hasNext()) {             ans.add(it.next());         }                   return ans;     } }   class NestedIntegerIterator implements Iterator<Integer> {     private Stack<NestedInteger> stack;           public NestedIntegerIterator(List<NestedInteger> nestedList) {         stack = new Stack<>();         fillStack(nestedList);     }           @Override     public Integer next() {         Integer ans = null;         if (hasNext()) {             ans = stack.pop().getInteger();         }         return ans;     }           @Override     public boolean hasNext() {         while (!stack.isEmpty() && !stack.peek().isInteger()) {             NestedInteger nestInteger = stack.pop();             fillStack(nestInteger.getList());         }                   return !stack.isEmpty();     }           @Override     public void remove() {               }           private void fillStack(List<NestedInteger> list) {         for (int i = list.size() - 1; i >= 0; i--) {             stack.push(list.get(i));         }     } }