Please do Compare Method Linked List file below and All the methods in the BigInteger file below the linkedlist file

import java.util.*;

import java.io.*;

public class LinkedList

{

int n;

ListNode start;

ListNode rear;

// You can set debug=true when you are debugging and want

// to print out what your program is doing.

// Please leave your debugging messages in your code when

// you submit it. Change debug back to false before

// submitting your code.

static final boolean debug= false;

public LinkedList()

{

n= 0;

start= null;

rear= null;

}

public LinkedList(int size, ListNode first, ListNode last)

{

n= size;

start= first;

rear= last;

}

public static LinkedList readBigInteger(Scanner in)

{

int y = readInteger(in);

if(y == -1) return null;

LinkedList x;

x = new LinkedList();

x.n = y;

if(x.n == 1) {

x.start = new ListNode(readInteger(in), null);

x.rear = x.start;

} else {

x.rear = new ListNode(readInteger(in), null);

x.start = new ListNode(readInteger(in), x.rear);

for(int i = 2; i < x.n; i++) {

x.start = new ListNode(readInteger(in), x.start);

}

}

return(x);

}

public void reverse(int level)

{

Test.checkList(this);

if(this.n == 1) { //Base case - checking list size

return;

} else { // Start of recursive call

ListNode temp = this.start; // Create temporary node at the beginning

for(int i = 0; i < this.n/2 - 1; i++) { // Traverse to middle of list

temp = temp.next;

}

LinkedList firstHalf = new LinkedList(this.n/2, this.start, temp); //Breaks list into two seperate list

int x = n - n/2; // Finds the middle point and makes it a starting point for the second list that has been split

LinkedList secondHalf = new LinkedList(x, temp.next, this.rear);

firstHalf.rear.next = null;

firstHalf.reverse(level + 1); // These four lines recursive calls it

secondHalf.reverse(level + 1);

secondHalf.rear.next = firstHalf.start;

this.start = secondHalf.start; // Merges the splitted list back together

this.rear = firstHalf.rear;

this.rear.next = null;

}

}

/*

Write a compare method in the class linkedList for comparing bigInteger values. Big integers can have leading zeroes.

If they do, please do not remove them (it is more interesting when we are analyzing time complexities to be forced to deal with them).

If you call it like this: x.compare(y) then it should return -1 if x < y, 0 if x=y, and +1 if x > y. For full marks, your routine should take O(n)

time to execute in the worst case where n is the maximum of x.n and y.n. Be careful when programming this to ensure that it still works correctly

if a bigInteger is compared to itself.

This method returns:

-1 if the bigInteger associated with the method is less than y

0 if the bigInteger associated with the method is equal to y

+1 if the bigInteger associated with the method is greater than y

*/

public int compare(LinkedList y)

{

// Insert your code for question 2 here.

return(0); // Delete this when you write your code.

}

// Tries to read in a non-negative integer from the input stream.

// If it succeeds, the integer read in is returned.

// Otherwise the method returns -1.

public static int readInteger(Scanner in)

{

int n;

try{

n= in.nextInt();

if (n >=0) return(n);

else return(-1);

}

catch(Exception e)

{

// We are assuming legal integer input values are >= zero.

return(-1);

}

}

// You can use this in order to get nicer output

// (lined up in columns).

public void printBigInteger(int nDigit)

{

boolean leadingZero;

ListNode current;

int i;

int n_extra;

reverse(0);

leadingZero= true;

if (n < nDigit)

{

for (i=n; i < nDigit; i++)

System.out.print(" ");

}

n_extra= n- nDigit;

current= start;

while (current != null)

{

if (leadingZero)

{

if (current.data != 0)

leadingZero= false;

}

if (leadingZero)

{

if (current.next == null) // value is 0.

System.out.print(current.data);

else if (n_extra <= 0)

System.out.print(" ");

}

else

{

System.out.print(current.data);

}

n_extra--;

current= current.next;

}

reverse(0);

}

}

All Big Integer method to do List: 

import java.util.*;

import java.io.*;

/* This class is for creating a singly linked class of big integer nodes. */

/* Hand this in together with your LinkedList.java. */

class BigIntegerList

{

int n; // Number of items in the list.

BigIntegerNode start;

BigIntegerNode rear;

// You can set debug=true when you are debugging and want

// to print out what your program is doing.

// Please leave your debugging messages in your code when

// you submit it. Change debug back to false before

// submitting your code.

static final boolean debug= false;

public BigIntegerList()

{

n=0;

start= null;

rear= null;

}

/*

Your method should read in an integer n followed by n big integers.

If the program has no more input when it tries to read in n, return null.

Otherwise, return a big integer list that contains the big integers in the

same order as they appear in the input stream. For full marks, your code

should run in O(n) time assuming that the big integers each have at most

some constant number of digits (in contrast to the lab 1 readRear code

which runs in O(n2) time).

*/

public static BigIntegerList readBigIntegerList(Scanner in)

{

BigIntegerList problem;

// Insert your code for Question 2 here.

return(null);

}

/*

This method prints a big integer list. To print a big integer x, use x.printBigInteger(8)

(code I gave you in LinkedList.java) so that the output is lined up nicely and easier to

read for your quickSort routine. Print the output so that only 10 values appear on each

line except possibly the last line (which may have less than 10 values). Ensure subsequent

output starts on a new line.

*/

public void printBigIntegerList()

{

// Insert your code for Question 3 here.

}

/*

The variable level is a debugging variable representing the level of recursion. This routine sorts a list of big integers by rearranging the pointers.

The pseudo code you should implement for this program is:

A list of size 0 or 1 is sorted so return if n is at most 1.

Set the pivot value to be the big integer value that appears first on the linked list.

Create 3 new lists, List1, List2 and List3.

Traverse the list removing each cell and placing it at the end of the appropriate list:

List1: for values less than the pivot.

List2: for values equal to the pivot.

List3: for values greater than the pivot.

Sort List1 and List3 recursively.

The final answer is List1 followed by List2 followed by List3

*/

public void quickSort(int level)

{

// Insert your code for Question 4 here.

}

}

List Node file:

/* This class defines a list node for a singly linked list of integers. Do not insert any code into this class. The automated testing of your program will include this code as it is given here. */ class ListNode{ public int data; public ListNode next; public ListNode(int x, ListNode ptr) { data= x; next= ptr; } } 

Big Integer Node file:

 /* This class defines a list node for a singly linked list of big integers. Do not insert any code into this class. The automated testing of your program will include this code as it is given here. */ class BigIntegerNode{ public LinkedList x; public BigIntegerNode next; public BigIntegerNode(LinkedList y, BigIntegerNode ptr) { x= y; next= ptr; } } 

Tester File:

// You can use this to start testing your program.

 import java.util.*; import java.io.*; // This program tests the routines students write for assignment // 2 Part B for CSC 225 in Fall 2012. public class Test { public static boolean checkList(LinkedList x) { // Fill in your code for this. return(true); } public static void main(String args[]) { int nCompareTest; LinkedList x, y; int cmp; int nSortTest; int problem_number; BigIntegerList problem; Scanner in = new Scanner(System.in); // Test the compare method. nCompareTest= LinkedList.readInteger(in); System.out.println("Testing the compare method: " + nCompareTest + " tests."); for (problem_number=1; problem_number <= nCompareTest; problem_number++) { x= LinkedList.readBigInteger(in); y= LinkedList.readBigInteger(in); System.out.print("Problem " ); if (problem_number < 10) System.out.print(" "); System.out.print(problem_number + ": "); cmp= x.compare(y); x.printBigInteger(8); if (cmp < 0) System.out.print(" < "); else if (cmp > 0) System.out.print(" > "); else System.out.print(" = "); y.printBigInteger(8); System.out.println(); } nSortTest= LinkedList.readInteger(in); System.out.println("-----------------------------------------------------"); System.out.println("Testing the quickSort method: " + nSortTest + " tests."); for (problem_number=1; problem_number <= nSortTest; problem_number++) { System.out.println("-----------------------------------------------------"); System.out.println("Sort Problem " + problem_number); problem= BigIntegerList.readBigIntegerList(in); System.out.println("Before Sorting:"); problem.printBigIntegerList(); problem.quickSort(0); System.out.println("After Sorting:"); problem.printBigIntegerList(); } } } 

Text file to Test code: to test do java Test < in.txt > out.txt

20

 8 0 0 0 0 9 0 0 0 8 0 0 0 0 0 9 0 0 8 0 0 0 0 0 9 0 0 8 0 0 0 0 9 0 0 0 5 1 0 0 0 0 4 1 0 0 0 4 1 0 0 0 5 1 0 0 0 0 5 0 0 1 0 0 3 1 0 0 3 0 0 1 5 0 0 0 0 1 2 1 0 5 0 0 0 1 0 3 0 0 1 5 0 0 0 0 1 5 8 7 6 5 4 5 9 7 6 5 4 5 8 7 6 5 4 5 8 9 6 5 4 5 8 7 6 5 4 5 8 7 9 5 4 5 8 7 6 5 4 5 8 7 6 9 4 5 8 7 6 5 4 5 8 7 6 5 9 5 5 3 2 1 0 5 4 3 2 1 0 5 4 5 2 1 0 5 4 3 2 1 0 5 4 3 5 1 0 5 4 3 2 1 0 5 4 3 2 5 0 5 4 3 2 1 0 5 4 3 2 1 5 5 4 3 2 1 0 12 1 2 3 4 5 6 7 8 9 0 1 2 12 1 2 3 4 5 6 7 8 9 0 1 2 16 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 16 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 6 1 5 1 4 1 3 1 2 1 1 1 0 6 1 0 1 1 1 2 1 3 1 4 1 5 7 1 3 1 1 1 5 1 4 1 2 1 0 1 6 10 2 3 5 2 3 4 2 4 5 2 5 7 2 5 6 2 1 3 2 6 7 2 1 2 2 6 8 2 4 6 9 2 3 4 2 1 2 2 5 6 2 1 2 2 5 6 2 3 4 2 1 2 2 3 4 2 5 6 9 6 3 4 5 6 7 8 6 4 5 6 7 8 9 6 1 2 3 4 5 6 6 4 5 6 7 8 9 6 1 2 3 4 5 6 6 3 4 5 6 7 8 6 3 4 5 6 7 8 6 1 2 3 4 5 6 6 4 5 6 7 8 9 8 8 1 4 4 4 4 4 4 9 8 0 1 4 4 4 4 4 9 8 0 0 1 4 4 4 4 9 8 0 0 0 1 4 4 4 9 8 0 0 0 0 1 4 4 9 8 0 0 0 0 0 1 4 9 8 0 0 0 0 0 0 1 9 8 0 0 0 0 0 0 0 9