Practice-It

Write a method of the LinkedIntList class called removeSmaller that removes the smaller value in each successive pair of numbers in the list, constructing and returning another LinkedIntList that contains the values removed. For example, suppose that a variable called list stores the following values:

        [100, 68, 102, 138, 20, 105, -128, 100]
          |   |    |    |    |   |     |    |
          +---+    +----+    +---+     +----+
          pair      pair     pair       pair

As indicated, this list has four pairs. If the following call is made:

        LinkedIntList result = list.removeSmaller();

then after the call, list and result would store the following values:

        list:   [100, 138, 105, 100]
        result: [68, 102, 20, -128]

Notice that for the first pair, the smaller value 68 has been moved to the second list while the larger value 100 has been retained in the original list. Similarly for the second pair, the value 102 has been moved to the second list while the value 138 has been retained in the original list.

If the two values in a pair are equal, you should remove the first one in the pair and retain the second one. If there is an odd number of values in the original list, the final value is retained in the original list. For example, if the list had instead stored these values:

        [87, 145, 189, 146, 140, 61, 66]

then after the call list and result would store the following values:

        list:   [145, 189, 140, 66]
        result: [87, 146, 61]

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. You will need to call the zero-argument LinkedIntList constructor to construct the list to be returned and 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, you may not use any auxiliary data structure to solve this problem (no array, ArrayList, stack, queue, String, etc), and your solution must run in O(n) time where n is the number of nodes in the list. You also may not change any data fields of the nodes. You MUST solve this problem by rearranging the links of the list.