X633: insertListInMiddle

Consider the following class definition:
   class Link{
      Object data;
      Link next;
   }
p is a reference to the first node of List L. q is a reference to the first node of List L'. Insert the second list in middle of the first list. Return a refernce to the first node of the new list. Make sure to account for edge cases! Take into consideration odd length lists and even length lists (look at examples).

Initial Setup	Final Configuration

Examples:

insertListInMiddle(Link.CreateList(1,2,3),Link.CreateList(4,5,6)) -> Link.CreateList(1,2,4,5,6,3)

insertListInMiddle(Link.CreateList(4,3,2,1),Link.CreateList(2)) -> Link.CreateList(4,3,2,1,2)

Your Answer:

Feedback