341. Flatten Nested List Iterator.md

341. Flatten Nested List Iterator

---

leetcode-cn Daily Challenge on March 23th, 2021.

---

Difficulty : Medium

Related Topics : Stack、Design

---

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Example 1:

Input: [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false,
             the order of elements returned by next should be: [1,1,2,1,1].

Example 2:

Input: [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false,
             the order of elements returned by next should be: [1,4,6].

---

Solution

• mine
  • Java
    • Runtime: 2 ms, faster than 98.22%, Memory Usage: 41.2 MB, less than 88.23% of Java online submissions

      // O(N) time
      // O(N) space
      LinkedList<Integer> list;
      public NestedIterator(List<NestedInteger> nestedList) {
          list = new LinkedList<>();
          dfs(list, nestedList);
      }
      
      void dfs(LinkedList<Integer> list, List<NestedInteger> nestedList){
          for(NestedInteger l : nestedList){
              if(l.isInteger()){
                  list.add(l.getInteger());
              }else{
                  dfs(list, l.getList());
              }
          }
      }
      
      @Override
      public Integer next() {
          return list.removeFirst();
      }
      
      @Override
      public boolean hasNext() {
          return !list.isEmpty();
      }
      

---

• the most votes

• Runtime: 1 ms, faster than 100.00%, Memory Usage: 41.4 MB, less than 71.65% of Java online submissions

  Stack<Iterator> stack;
  Iterator<NestedInteger> it;
  NestedInteger ni;
  
  public NestedIterator(List<NestedInteger> nestedList) {
      this.stack = new Stack<>();
      this.it = nestedList.iterator();
  }
  
  @Override
  public Integer next() {
      hasNext();
      Integer res = ni.getInteger();
      ni = null;
      return res;
  }
  
  @Override
  public boolean hasNext() {
      if (ni != null) {
          return true;
      }
      if (it.hasNext()) {
          NestedInteger next = it.next();
          if (next.isInteger()) {
              ni = next;
              return true;
          } else {
              stack.push(it);
              List<NestedInteger> nextList = next.getList();
              it = nextList.iterator();
              return hasNext();
          }
      } else if (!stack.isEmpty()) {
          it = stack.pop();
          return hasNext();
      } else {
          return false;
      }
  }
  

---