Question

Write a member method named countMin.  This method is inside the class SingleLinkedList<E>. So it has the direct access to Node<E> class and data fields head, size. This method counts how many times the smallest data item in this SingleLinkedList<E> appears in the list.  It is assumed that the class passed to E implements the Comparable<E> interface.

public int countMin()

----------------------

Write a method named endWith.  This method is OUTSIDE the class LinkedList<E>. It takes in two parameters: two LinkedList of Integers named list1, list2. It checks if list1 ends with list2, and returns true if yes, false otherwise.  list1 ends with list2 if list2 is identical to the tail of list1. For example, list1 below ends with list2 below.

list1:  100 80 200 250 30 20 35

list2:  30  20  35

public static boolean endWith(LinkedList<Integer> list1, LinkedList<Integer> list2)

----------------

Write a method named changeStack that takes in a Stack of Integer objects named stackIn as a parameter and returns another Stack of Integer objects. The returned Stack contains contents that is the result of switching the top half and the bottom half of the stackIn. But the ordering of integers in each half is NOT changed. In the case of odd-size stackIn, the middle element remains in the same position before and after the switch.

This method is OUTSIDE the class <E>.

Example 1:

                  stackIn                   Returned Stack

   top                                                               top     

                    30                                     100

                    10                                     50

                    100                                   30

   bottom    50                                     10        bottom

Example 2:

                  stackIn                   Returned Stack

   top                                                                top     

                    15                                     65

                    3                                       8

                    200                                   200

                  65                                     15     

bottom      8                                        3        bottom

The Stack class includes all methods necessary for the stack operations. You can consider Stack is like the ArrayDeque in Java API used as a Stack.

public static Stack<Integer> changeStack(Stack<Integer> stackIn)

Answer 1

Solution

1. Write a member method:

public int countMin() {
int min_val = head.value;
Node<E> curr = head;
int count = 0;
for(int i=0;i<size;i++) {
if(curr.value < min_val) {
min_val = curr.value;
count = 1;
}
else {
count++;
}
curr = curr.next;
}
return count;
}

2 write a method endwith

public static boolean endsWith(LinkedList<Integer> list1,LinkedList<Integer> list2) {
Node<Integer> h1 = list1.head,h2 = list2.head;
int extra = lis11.size - list2.size;
if(extra < 0) {
return false;
}
while(extra--) {
h1 = h1.next;
}
int sz = h2.size;
while(sz--) {
if(h1.value != h2.value) {
return false;
}
h1 = h1.next;
h2 = h2.next;
}
return false;
}

3 write a method name changed stack

public static Stack<Integer> changeStack(Stack<Integer> stackIn) {
int sz = stackIn.size;
  
Stack<Integer> stackOut = new Stack<Integer>(sz);
boolean flag = true;
if(sz%2 == 0)
flag = false;
sz = sz/2;
Stack<Integer> stacktmp = new Stack<Integer>(sz);
for(int i=0;i<sz;i++) {
stactmp.push(stackIn.top());
stackIn.pop();
}
for(int i=0;i<sz;i++) {
stackOut.push(stacktmp.top());
stacktmp.pop();
}
if(flag) {
stackOut.push(stackIn.top());
stackIn.pop();
}
for(int i=0;i<sz;i++) {
stactmp.push(stackIn.top());
stackIn.pop();
}
for(int i=0;i<sz;i++) {
stackOut.push(stacktmp.top());
stacktmp.pop();
}
return stackOut;
}