Спрятать связанный список в Java

Question

Я пытаюсь свернуть многоуровневый связанный список. Учитывая связанный список, где каждый узел представляет собой связанный список и содержит два указателя его типа: (i) Указатель на следующий узел в основном списке (мы называем его «правильным» указателем в нижнем коде) (ii) Указатель на связанный список, где этот узел является головкой (мы называем его «вниз» указателем в нижнем коде). Всего связанных списков сортируются

5 -> 10 -> 19 -> 28 
    | |  |  | 
    V V  V  V 
    7 20 22 35 
    |   |  | 
    V   V  V 
    8   50 40 
    |    | 
    V    V 
    30    45 

К

5 7 8 10 19 20 22 28 30 35 40 45 50 

ниже мой Java-код:

public class FlattenAList { 
public static MultiNode<Integer> end = new MultiNode<Integer>(0); 
public static MultiNode<Integer> result = end; 

public static MultiNode flatten(MultiNode head) { 
    if (head == null || head.right == null) 
     return head; 
    MultiNode<Integer> tmp = head; 

    while (tmp != null) { 
     merge(tmp, result); 
     tmp = tmp.right; 
    } 
    return result; 
} 

public static void merge(MultiNode<Integer> a, MultiNode<Integer> b) { 
    if (a == null) { 
     end.down = b; 
     end = end.down; 
     return; 
    } 
    if (b == null) { 
     end.down = a; 
     end = end.down; 
     return; 
    } 

    if (a.data <= b.data) { 
     end.down = a; 
     end = end.down; 
     merge(a.down, b); 
    } else { 
     end.down = b; 
     end = end.down; 
     merge(a, b.down); 
    } 
} 
} 

Функция слияния испытывают проблемы, я получаю java.lang. StackOverflowError at java.lang.Integer.intValue (Неизвестный источник)

в если (a.data < = b.data)

Answer 1

Это быстрый простой способ о том, как сделать это в соответствии с вашими потребностями.

package example; 

public class FlattenAList { 

    private static MultiNode<Integer> merge(MultiNode<Integer> a, MultiNode<Integer> b) { 
     MultiNode<Integer> head = new MultiNode<Integer>(); 
     MultiNode<Integer> temp = head; 
     while (a != null && b != null) { 
      if (a.data < b.data) { 
       temp.down = a; 
       temp = temp.down; 
       a = a.down; 
      } else if (b.data < a.data) { 
       temp.down = b; 
       temp = temp.down; 
       b = b.down; 
      } 
     } 

     temp.down = (a == null) ? b : a; 
     return head.down; 
    } 

    static class MultiNode<T> { 
     T data; 
     MultiNode<T> right; 
     MultiNode<T> down; 

     public MultiNode(T data) { 
      this.data = data; 
     } 

     public MultiNode() { 

     } 
    } 

    public static MultiNode<Integer> flatten(MultiNode<Integer> root) { 

     MultiNode<Integer> temp = root; 
     MultiNode<Integer> result = null; 
     while (temp != null) { 
      result = merge(temp, result); 
      temp = temp.right; 
     } 
     return result; 
    } 

    public static void print(MultiNode<Integer> start) { 
     while (start != null) { 
      System.out.print(start.data+" "); 
      start = start.down; 
     } 
    } 

    public static void main(String[] args) { 
     MultiNode<Integer> start = new MultiNode<Integer>(5); 
     start.right = new MultiNode<Integer>(10); 
     start.right.right = new MultiNode<Integer>(19); 
     start.right.right.right = new MultiNode<Integer>(28); 

     start.down = new MultiNode<Integer>(7); 
     start.down.down = new MultiNode<Integer>(8); 
     start.down.down.down = new MultiNode<Integer>(30); 

     start.right.down = new MultiNode<Integer>(20); 

     start.right.right.down = new MultiNode<Integer>(22); 
     start.right.right.down.down = new MultiNode<Integer>(50); 

     start.right.right.right.down = new MultiNode<Integer>(35); 
     start.right.right.right.down.down = new MultiNode<Integer>(40); 
     start.right.right.right.down.down.down = new MultiNode<Integer>(45); 
     // Node result = flatten(start); 
     MultiNode<Integer> result = flatten(start); 
     print(result); 
    } 
} 

Выход:

5 7 8 10 19 20 22 28 30 35 40 45 50