8. corrupt(): In the LinkedList.java write a method that corrupts a given ordinary linked list by changing the last nodes forward pointer (which is supposed to be null) to point to a node at the given index. In Figure 1 a clean list is shown. In Figure 2, its corrupted version is shown. The task in corrupt() is to convert a clean linked list to a corrupted one. The position to corrupt is determined by the line

   index = r1.nextInt(list1.getSize()/2);

   which chooses the corruption index from the first half of the linked list.

9. findCorruption(): In the LinkedList.java write a method that finds if the linked list contains a loop (This is a popular software interview question).

   • In the main class, a sorted list is given as the parameter to this method (for ease of debugging). Do not use the sorted nature of the linked list to detect the corruption.

   • Do not store visited nodes to detect a loop. That would be a very lazy solution. If the linked list is big, you would store too much information.

10. public class LinkedList { public class Node { public int item; public Node next; public Node( int newItem, Node newNext ) { item = newItem; next = newNext; } } private Node last; private int nodeCount; private static Random generator = new Random(System.nanoTime()); public LinkedList() { last = null; nodeCount = 0; } public int getSize() { return nodeCount; } private void insertNode( Node newNode ) { if ( nodeCount == 0 ) { newNode.next = newNode; last = newNode; } else { newNode.next = last.next; last.next = newNode; } nodeCount++; } void insertValue(int newItem) { Node newNode = new Node( newItem, null ); if ( nodeCount == 0 ) { newNode.next = newNode; last = newNode; } else { newNode.next = last.next; last.next = newNode; } nodeCount++; } /* corrupt: expects an ordinary linked list with a null pointer in the last node. The latest inserted node sits at index 0. Take the last node in the linked list and change its pointer to the node at the given index. return the value of the corruption index. */ public int corrupt(int index) { int valOfCorruptedNode=Integer.MIN_VALUE; //write your code here return valOfCorruptedNode; }//end of corrupt /* findCorruption: find if the linked list contains a loop. Corruption is defined as the last node not having a null pointer, but instead pointing to a node in the linked list as its forward node. A circular link is due to a corruption. Do not use the sorted order of the linked list to detect the corruption. A popular interview question, the solution to this question is known as the Floyds Cycle-Finding Algorithm. A more difficult version would ask the index/value of the corruption. */ public boolean findCorruption() { //write your code here // Do not store visited nodes to detect a loop. // Because if the linkedlist is big, you would store too much information. return false; }//end of findCorruption /* reset: Remove every node from the linked list. Do not forget the nodeCount variable. */ public void reset() { //write your code here. }// end of reset /* deleteOddNodes: delete nodes that have an odd item value. Reassign pointers. Do not create a new linked list. */ public void deleteOddNodes() { //write your code here }//end of deleteOddNotes /* hasDummies: checks if the linked list has 1) a dummy header with Integer.MIN_VALUE and a dummy trailer with Integer.MAX_VALUE. */ public boolean hasDummies() { //write your code here //change return type yourself return false; }//end of hasDummies /* isOrdinary: checks the type of this list. If the list is in a given type, it returns true, otherwise false. if the list empty, return false. Use the nodecount variable to detect the end */ public boolean isOrdinary( ) { //write your code here //change return type yourself return false; }//end of isOrdinary /* isCircular: checks the type of this list. If the list is circular, it returns true, otherwise false. if the list empty, return false. Use the nodeCount variable to detect the end */ public boolean isCircular( ) { //write your code here //change return type yourself return false; }//end of isCircular /* addDummies: add a dummy header and a dummy trailer to the linked list. Use Integer.MIN_VALUE and Integer.MAX_VALUE */ public void addDummies() { // write your code here }//end of addDummies /*********************************************** * * convertCircularToOrdinary: Convert the list to an ordinary * linked list (a single linked list without dummy header or trailer). * use the existing last pointer and rewrite * its address to point to the first node. Update the last node's forward pointer as well. * This linked list class is originally written for a circular linked list, * DO NOT CHANGE THE ORIGINAL INSERT OR DELETE METHODS. ************************************************/ public void convertCircularToOrdinary() { //write your code here }//end of convertCircularToOrdinary /*********************************************** * convertOrdinaryToCircular: Convert the list to a circular * linked list (without a dummy header or trailer). ************************************************/ public void convertOrdinaryToCircular() { //write your code here }//end of convertOrdinaryToCircular /*********************************************** * * add: Take the values in the parameter list2 * and insert them into this list in an order-preserving manner (keep the order as it is in list1). * The list2 should not change. Both lists are circular single linked lists (no dummies) * ************************************************/ public void add(LinkedList list2) { //write your code here. List1 and list2 can contain duplicate values. } private Node choosePivot( ) { int randomIndex = generator.nextInt( nodeCount ); Node prev = last; Node pivot; int i; // Find the node before the pivot for ( i = 0; i <= randomIndex; i++ ) prev = prev.next; pivot = prev.next; if ( last == pivot ) last = prev; prev.next = pivot.next; nodeCount--; return pivot; } public LinkedList partition( Node pivot ) { Node curr; LinkedList smalls = new LinkedList(); LinkedList bigs = new LinkedList(); int size = nodeCount; int i; for ( i = 0; i < size; i++ ) { curr = last.next; last.next = last.next.next; nodeCount--; if ( curr.item < pivot.item ) { // curr belongs in the smalls smalls.insertNode( curr ); } else { // curr belongs in the bigs. bigs.insertNode( curr ); } } last = bigs.last; nodeCount = bigs.nodeCount; return smalls; } private void rejoin( LinkedList smalls, Node pivot ) { Node firstBig; smalls.insertNode( pivot ); // insert pivot at front smalls.last = smalls.last.next; // pivot should be last node if ( nodeCount != 0 ) { firstBig = this.last.next; this.last.next = smalls.last.next; pivot.next = firstBig; nodeCount = nodeCount + smalls.nodeCount; } else { this.last = smalls.last; nodeCount = smalls.nodeCount; } } public void quickSort( ) { Node pivot; LinkedList smalls; if ( nodeCount > 2 ) { pivot = choosePivot(); // removes a pivot smalls = partition( pivot ); // bigs in original list smalls.quickSort( ); quickSort( ); // recursively quick sort the bigs rejoin( smalls, pivot ); // rejoin into one circular list } if ( nodeCount == 2 ) { if ( last.item < last.next.item ) { // swap them: first becomes last last = last.next; } } } public boolean isSorted() { boolean sorted = true; Node curr = last.next; if ( nodeCount > 1 ) { do { if ( curr.next.item < curr.item ) sorted = false; curr = curr.next; } while ( ( curr != last ) && sorted ); } return sorted; } public void printList() { Node curr; if (nodeCount > 0) { curr = last.next; do { System.out.println( curr.item ); curr = curr.next; } while ( curr != last.next ); } }