Homework 6

Write a method that takes two linked lists L1 and L2, both in order, and returns a list, also in order, containing all the numbers in L1 and L2. If one lists is empty, the other list is the answer. If both lists are non-empty, compare L1.item and L2.item. If L1.item is smaller, it is the smallest number of all, and it becomes the first number in the answer list. To find the tail of the answer, recursively combine the tail of L1 with L2. If L2.item is smaller, use the same idea with l1 and l2 changing places. You must use the same IntList class that I have used in the lectures. Sample behavior:

list of integers: 1 3 5
list of integers: 2 4 6
answer: 1 2 3 4 5 6

Possible Solution:
Compile two files in the same folder:
                             javac list.java
                            javac homework6.java
Then run:    java homework6

 1/ list.java

class list
{
     public int first;
     public list rest;
   
     public list(int x, list y)
    {
        first = x;
        rest = y;
    }
}

2/ homework6.java

public class homework6
{

 public static void main(String[] args)
 {
   list L1 = new list(1, new list(3, new list(5, null)));
   list L2 = new list(2, new list(4, new list(6, null)));
   list L = merge(L1, L2);
 
   System.out.print("list of integers: ");
   show_list(L1);
   System.out.println();
   System.out.print("list of integers: ");
   show_list(L2);
   System.out.println();
   System.out.print("answer: ");
   show_list(L);
   System.out.println();
 }

static list merge(list x, list y)
{
  if (x == null)
    return y;
  else if (y == null)
    return x;
  else
  {
    if (x.first < y.first)
      return new list(x.first, merge(x.rest, y));
    else
      return new list(y.first, merge(x, y.rest));
  }
}
 

 static void show_list(list y)
 {
  if(y != null)
  {
   System.out.print(y.first + " ");
   show_list(y.rest);
  }
 }
}