Practice-It

Write a method of the LinkedIntList class called mergeFrom that takes a list of integers as a parameter and that moves the values from the second list into the first list so as to preserve sorted order assuming that the two lists are in sorted (nondecreasing) order initially. The resulting list should contain the values from both lists in sorted order and the list passed as a parameter should be empty after the call. For example, if the variables list1 and list2 store the following:

        list1 = [-3, 0, 9, 12, 43, 54], list2 = [9, 9, 15, 98]

and you make the following call:

        list1.mergeFrom(list2);

then the lists should store the following values after the call:

        list1 = [-3, 0, 9, 9, 9, 12, 15, 43, 54, 98], list2 = []

Notice that list2 is empty after the call and that the values that were in list2 have been moved into list1 so as to preserve sorted order. If the call instead had been list2.mergeFrom(list1) then the result would be:

        list1 = [], list2 = [-3, 0, 9, 9, 9, 12, 15, 43, 54, 98]

Either list might be empty, as in:

        list1 = [5, 7, 7, 12, 15], list2 = []

in which case the call list1.mergeFrom(list2) would leave the lists unchanged while list2.mergeFrom(list1) would leave you in this state:

        list1 = [], list2 = [5, 7, 7, 12, 15]

You are writing a public method for a linked list class defined as follows:

        public class ListNode {
            public int data;       // data stored in this node
            public ListNode next;  // link to next node in the list

            
        }
 
        public class LinkedIntList {
            private ListNode front;

            
        }

You are writing a method that will become part of the LinkedIntList class. Both lists are of type LinkedIntList. You may define private helper methods to solve this problem, but otherwise you may not assume that any particular methods are available. You are allowed to define your own variables of type ListNode, but you may not construct any new nodes, and you may not use any auxiliary data structure to solve this problem (no array, ArrayList, stack, queue, String, etc). You also may not change any data fields of the nodes. You MUST solve this problem by rearranging the links of the lists. Your solution must run in O(n) time where n is the length of the merged list. As in the examples above, assume that both lists are in sorted order.