Как бы я рекурсивно объединить два списка?

Question

Я понял, как рекурсивно обратить вспять один список, но я пытаюсь выяснить, как объединить два списка, используя рекурсию.

Избегайте использования коллекций.

Вот как это делается, чтобы отменить список, но я много стараюсь, как объединить два, и я не могу понять это вообще, поэтому я прошу людей более опытных их.

public class Test { 

    public static class Node { 



      public Node next; 
      public String name; 

      public Node(String name) { 
        this.name = name; 
      } 

    } 

    public static void reverse(Node previous, Node current) { 

     if (current.next != null) { 

      Node next= current.next; 
      reverse(current, next); 
     } 

      if (previous == null) { 
      // this was the start node 
        current.next= null; 
     } else { 
      //reverse 
      current.next= previous; 
     } 


    } 


    public static void main(String[] args) throws IOException, InterruptedException { 

      Node n1= new Node("A"); 
      Node n2= new Node("B"); 
      Node n3= new Node("C"); 
      Node n4= new Node("D"); 


      n1.next= n2; 
      n2.next= n3; 
      n3.next= n4; 


      Node cursor= n1; 
      while (cursor != null) { 
        System.out.println(cursor.name); 
        cursor= cursor.next; 
      } 


      reverse(null, n1); 

      cursor= n4; 
      while (cursor != null) { 
        System.out.println(cursor.name); 
        cursor= cursor.next; 

Я совершенно в тупике. Даже если я не заслуживаю полного ответа, я просто хотел бы указать в правильном направлении.

Answer 1

public class Test1 { 
    public static void main(String args[]) throws IOException { 
     List<Integer> list1 = new ArrayList<Integer>(); 
     list1.add(2); 
     list1.add(5); 
     list1.add(8); 

     List<Integer> list2 = new ArrayList<Integer>(); 
     list2.add(1); 
     list2.add(4); 
     list2.add(9); 

     List<Integer> mergeList = mergeList(list1, list2); 
     System.out.println(Arrays.asList(mergeList)); 
    } 

    private static List<Integer> mergeList(List<Integer> list1, List<Integer> list2) { 
     if (list1.size() == 0) 
      return list2; 
     if (list2.size() == 0) 
      return list1; 

     ArrayList result = new ArrayList<Integer>(); 

     if (list1.get(0) < list2.get(0))// sorting 
      result.add(list1.remove(0)); 
     else 
      result.add(list2.remove(0)); 

     result.addAll(mergeList(list1, list2)); 

     return result; 
    } 
} 

отсортирован

[[1, 4, 9, 2, 5, 8]]