Donate. I desperately need donations to survive due to my health

Get paid by answering surveys Click here

Click here to donate

Remote/Work from Home jobs

Merge 2 Linked List (sorted)

So my task is to make a merge method, which follows this... A method merge(Node parameter) which merges the parameter list with ‘this’ list. This method should only be called if both these lists are already sorted. This method should merge these two lists and return the merged result

I have this so far.

import java.util.Queue;
import java.util.Random;
import java.util.LinkedList;
public class Node<T extends Comparable<? super T>>
{

protected T head;
protected Node<T> tail;
LinkedList orderList = new LinkedList<>();
public Node(T h, Node<T> t) {
    head = h;
    tail = t;
}

public String toString() {
    if (tail == null) return "[" + head + "]";
    return "[" + head + tail.tailString();
}

private String tailString() {
    String initialPart= "," + head;
    if (tail==null) return initialPart + "]";
    return initialPart + tail.tailString();
}

public int length() {
    int result=1;
    for (Node<T> n=tail; n!=null; n=n.tail) { result++; }
    return result;
}

public Queue<Node<T>> queueSortedSegments() {
    Node<T> first = null;
    Node<T> last;
    Node<T> n = this;
    while (n!= null) {
        if (n.tail != null) {
            last = n;
            Node<T> current=last.tail;
            while(last.tail!=null) {
                if(last.head.compareTo(current.head)>0){
                    first = current;
                    last.tail = null;
                    orderList.add(n);
                }
                else{
                    last = current;
                    if(current.tail==null){
                        orderList.add(n);
                        first = null;
                    }
                }
                current=current.tail;
            }
        }
        else{
            orderList.add(n);
            first = null;
        }
        n=first;
    }
    return orderList;
}
//return null; //keep compiler happy

public boolean isSorted() {
    //this method should check whether 'this' list is already sorted
    for (Node<T> n = this; n.tail!=null; n=n.tail)
    {
        if(n.head.compareTo(n.tail.head) > 0)
        {

            return false; //keep compiler happy for now
        }
    }
    return true;
}

public Node<T> merge (Node<T> another){
    //this method should merge two sorted linked lists
    //and return their merged resulting list
    //the above are our assumptions about those lists

    assert isSorted();
    assert another==null || another.isSorted();


    return this;
}

public Node<T> mergeSort() {
    //this method should sort the list in the following way:
    //split the list up into sorted segments and place these into a queue
    //poll pairs of lists from the queue, merge them, and put their merge
    //back into the queue
    //if there is only one list left in the queue that should be returned
    Queue<Node<T>> queueSort =  queueSortedSegments();
    while ((queueSort.size()) >1)
    {
        Node<T> one = queueSort.poll();
        Node<T> two = queueSort.poll();
        queueSort.add(one.merge(two));
    }

    return queueSort.poll(); //keep compiler happy
}

static public Node<Integer> randomList(int n) {
    //for testing purposes we want some random lists to be sorted
    //the list is n elements long
    //the elements of the random list are numbers between 0 and n-1
    Random r=new Random();
    Node<Integer> result=null;
    int k=n;
    while(k>0) { 
        result=new Node<Integer>(r.nextInt(n),result);
        k--;
    }
    return result;
}

static public void test(int n) {
    //this method should do the following:
    //2. output it
    //3. report whether the 'isSorted' method thinks the list is sorted or 
    not
    //4. sort the list using mergeSort
    //5. output the sorted list
    //6. report whether the 'isSorted' method thinks that list is sorted or 
    not
    Node<Integer> test = randomList(n);//1. create a random linked list of 
    length n
    System.out.println(test);
    System.out.println("The List of integers has been sorted" + 
    test.isSorted());
    test = test.mergeSort();
    System.out.println(test);
    System.out.println("This integer has been sorted" + test.isSorted());

 }
 }

I havent a clue how to do the merge method

Comments