Question

Add a sort instance method to the IntList class, so that x.sort() returns an IntList that is a version of the IntList x, sorted in non-decreasing order. You may use any sorting algorithm you like. There should be no side effect on x.

//IntList Class

public class IntList {

private ConsCell start;

public IntList(ConsCell s) {

start = s;

}

public IntList cons (int h) {

return new IntList(new ConsCell(h,start));

}

public int length() {

int len = 0;

ConsCell cell = start;

while (cell != null) {

len++;

cell = cell.getTail();

}

return len;

}

public void print() {

System.out.print("[");

ConsCell a = start;

while (a != null){

System.out.print(a.getHead());

a = a.getTail();

if (a != null) System.out.print(",");

}

System.out.println("]");

}

public static void sort(int[] ConsCell) {

}

}

// ConsCell Class

/**

* A ConsCell is an element in a linked list of

* ints.

*/

public class ConsCell {

private int head;

private ConsCell tail;

public ConsCell(int h, ConsCell t) {

head = h;

tail = t;

}

public int getHead() {

return head;

}

public ConsCell getTail() {

return tail;

}

public void setTail(ConsCell t) {

tail = t;

}

}

//Main Class

public class Main {

public static void main(String args[]){

IntList a = new IntList(null);

IntList b = a.cons(2);

IntList c = b.cons(1);

IntList d = c.cons(3);

int x = a.length() + b.length() + c.length() + d.length();

a.print();

b.print();

c.print();

d.print();

System.out.println(x);

}

}

Answer 1

IntList class-

public class IntList {

    private ConsCell start;
    
    public IntList(ConsCell s) {
    
    start = s;
    
    }
    
    public IntList cons (int h) {
    
    return new IntList(new ConsCell(h,start));
    
    }
    
    public int length() {
    
    int len = 0;
    
    ConsCell cell = start;
    
    while (cell != null) {
    
    len++;
    
    cell = cell.getTail();
    
    }
    
    return len;
    
    }
    
    public void print() {
    
    System.out.print("[");
    
    ConsCell a = start;
    
    while (a != null){
    
    System.out.print(a.getHead());
    
    a = a.getTail();
    
    if (a != null) System.out.print(",");
    
    }
    
    System.out.println("]");
    
    }
    
    public static void sort(int[] ConsCell) {
    
    }

    public IntList sort(){

        // Make a duplicate copy of list which will be returned after sorting.
        ConsCell newStart = new ConsCell(start.getHead(), null);
        // temp element to iterate over list.
        ConsCell temp = start.getTail();
        // temp element at end of duplicate list.
        ConsCell temp2 = newStart;

        while(temp != null){
            ConsCell current = new ConsCell(temp.getHead(), null);
            temp2.setTail(current);

            temp2 = temp2.getTail();
            temp = temp.getTail();
            
        }

        IntList list = new IntList(newStart);
        int n = list.length();
        
        
        
        for(int i=0 ; i < n - 1 ; i++){
            ConsCell tempStart = newStart;
            for(int j = 0; j < n - i - 1 ; j++){
                ConsCell tempNext = tempStart.getTail();
                if(tempStart.getHead() > tempNext.getHead()){
                    int tempVal = tempStart.getHead();
                    tempStart.setHead(tempNext.getHead());
                    tempNext.setHead(tempVal);
                }
                tempStart = tempStart.getTail();
            }
        }
        
        return list;
        
    }
    
}
    
    

ConsCell class-

public class ConsCell {
    
    private int head;
    
    private ConsCell tail;
    
    public ConsCell(int h, ConsCell t) {
    
    head = h;
    
    tail = t;
    
    }
    
    public int getHead() {
    
    return head;
    
    }
    
    public ConsCell getTail() {
    
    return tail;
    
    }
    
    public void setTail(ConsCell t) {
    
    tail = t;
    
    }

    public void setHead(int h){
        head = h;
    }
    
    }

Main class -

import java.util.List;

public class IntList {

    private ConsCell start;
    
    public IntList(ConsCell s) {
    
    start = s;
    
    }
    
    public IntList cons (int h) {
    
    return new IntList(new ConsCell(h,start));
    
    }
    
    public int length() {
    
    int len = 0;
    
    ConsCell cell = start;
    
    while (cell != null) {
    
    len++;
    
    cell = cell.getTail();
    
    }
    
    return len;
    
    }
    
    public void print() {
    
    System.out.print("[");
    
    ConsCell a = start;
    
    while (a != null){
    
    System.out.print(a.getHead());
    
    a = a.getTail();
    
    if (a != null) System.out.print(",");
    
    }
    
    System.out.println("]");
    
    }
    
    public static void sort(int[] ConsCell) {
    
    }

    public IntList sort(){

        // To sort, we iterate n times over the list, and at each step we find the number which is just greater than
        // last element the list which we are building.

        ConsCell newStart = null;

        int n = length();

        ConsCell temp = start;
        
        // Set the smallest element to be the start of the new list.
        int last = start.getHead();

        while(temp != null){
            last = Math.min(last, temp.getHead());
            temp = temp.getTail();
        }

        newStart = new ConsCell(last, null);

        ConsCell tempTail = newStart;
        // Now we do n-1 iterations, and in each iteration we find the smallest number
        // that is larger than the tail of our new list and add the number at the end of list.
        for(int i=1;i<n;i++){
            last = tempTail.getHead();
            temp = start;
            int ceil = 10000000;

            while(temp != null){
                if(temp.getHead() > last && temp.getHead() < ceil ){
                    ceil = temp.getHead();
                }
                temp = temp.getTail();
            }

            // We need to attach ceil at the end of our list.

            ConsCell tail = new ConsCell(ceil, null);
            tempTail.setTail(tail);
            tempTail = tempTail.getTail();

        }
        // Return the new IntList with newStart as its start.
        return new IntList(newStart);
    }
    
}
    
    

Main class -

//Main Class
    
public class Main {
    
    public static void main(String args[]){
    
    IntList a = new IntList(null);
    
    IntList b = a.cons(2);
    
    IntList c = b.cons(1);
    
    IntList d = c.cons(100);
    
    d = d.cons(5);
    d = d.cons(12);
    d = d.cons(3);
    
    int x = a.length() + b.length() + c.length() + d.length();
    
    a.print();
    
    b.print();
    
    c.print();
    
    d.print();
    
    IntList sorted = d.sort();
    
    sorted.print();
    
    }
    
    }

The output is as follows -

The code has been commented for better readability. Please consider dropping an upvote to help out a struggling college kid :)

Happy Coding!!