(Dividing a linked list into two sublists of almost equal sizes) a. Add the oper

Question

(Dividing a linked list into two sublists of almost equal sizes)

a. Add the operation splitMid to the class LinkedListClass as follows:

public void splitMid(LinkedListClass<T> sublist);
//This method splits the given list into two sublists
//of (almost) equal sizes.
//Precondition: The list must exist.
//Postcondition: first points to the first node and last
// points to the last node of the first sublist.
// sublist.first points to the first node and
//sublist.last points to the last node of the second
//sublist.
Consider the following statements:
UnorderedLinkedList<Integer> myList;
UnorderedLinkedList<Integer> subList;
Suppose myList points to the list with elements 34 65 27 89 12 (in this order). The
statement:
myList.splitMid(subList);
splits myList into two sublists: myList points to the list with the elements 34, 65, 27,
and subList points to the sublist with the elements 89 12.
b. Write the definition of the method splitMid. Also
write a program to test your method. Use either the class UnorderedLinkedList or the class OrderedLinkedList to test your method.

Explanation / Answer

public void splitMid(LinkedList sublist){ int i = 0; Node first = firstNode; Node last = firstNode; Node sublistFirst; Node sublistLast; for (Node curr = firstNode; curr != null; curr = curr.next) { //traverses whole list i++; if((i%2 == 1) && (i > 1)){ //if the length of the array (that has been looked at so far) is odd, advance the end of the first half by one--this makes it so you only have to traverse once instead of twice. last = last.next; } sublistLast = curr; //if you have a class variable pointing to the end of the whole list, just set sublistLast equal to that and delete this line. } sublistFirst = last.next; last.next = null; //severs the connection between the first sublist and the second sublist. } //here is a method to test with. It just prints out the list: public void display(Node first, Node sublistFirst) { for (Node curr = first; curr != null; curr = curr.next) { System.out.println(curr.data); } System.out.println(); for (Node curr = sublistFirst; curr != null; curr = curr.next) { System.out.println(curr.data); } }

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---