Сортировка слиянием со связанным списком

Question

Я пытаюсь создать программу для своего класса по информатике, которая берет связанный список и сортирует его с помощью алгоритма сортировки слиянием.У меня возникают трудности с получением связанного списка и рекурсивным разбиением узлов путем поиска среднего узла.У меня есть три класса, один для моего узла, моего списка и для класса сортировки слиянием.

static Mynode h;
static Mylist list = new Mylist();

public static void Sort(String[] list){
}

public static void main(String[] args){
    /*
    node sort(node h);
    node l2 = split(h);
    */
    list.insert("cat");
    list.insert("ok");
            list.insert("ok");

    list.printdata();
    split(list);
}

public void sort(){
    String head;
}
public static void merge(Mylist list, int right, int left){

}
public static void split(Mylist list){
    Mynode tempFast = h;
    Mynode tempslow = h;        
    Iterator iterator = tempFast.iterator();
    Iterator iterator = tempslow.iterator();

        while(tempslow.getNext()!=null && tempslow.getNext()!=null){
            tempFast.getNext();
            tempFast.getNext();
            tempslow.getNext();
        }
}

public Merge(String data){
    /*
    this.data = data; 
    */
}

/*
public Node msort(String r){

}
    /*
    node l2 = split(h);
    h = msort(h);
    l2 = msort(l2);
    return merge(h, l2);
    */
}

// input: java myms < word3
// output: Unsorted: cow, zebra, ant || Sorted: ant, cat, zebra

static Mynode h;
public Mylist(){
    this.h = null;
}

public void insert(String s) {
//method for node insertion
   this.h = new Mynode(s, this.h);
}
public boolean contains(String s){
//method for identifying contains specific data
    Mynode temp = this.h;
    while(temp !=null){
    //while the node contains a value
        if(s.equals(temp.getData())){
        //if the node contains the specified data, return true
            return true;
        }
        temp = temp.getNext();
        //set the node reference to the next value
    }
    return false;
}
public void printdata(){
    Mynode temp = this.h;
    while(temp !=null){
        System.out.println(temp.getData());
        //print the current node, then increment the temp node one over
        temp = temp.getNext();
    }
}
public void deletion (String s){
//method for deletion
    Mynode temp = this.h;
    Mynode previous = null;
    if (temp != null && temp.getData().equals(s)) {
    //when node contains data and the specified data matched the node in the linked list 
        this.h = temp.getNext();
        //node reference is set to the next value
        return; 
    } 
    while (temp != null && !(temp.getData().equals(s))) { 
    //retrieve node reference for next value
        previous = temp; 
        temp = temp.getNext(); 
        //set node to the next value
    } 
    if(temp ==null) {
        return;
    }
    previous.setNext((temp.getNext())); 

}
public Iterator iterator() {
    return new Myiter(this.h);
}
private class Myiter implements Iterator {

    private Mynode temp;

    public Myiter(Mynode temp) {
        this.temp = h;
    }
    public boolean hasNext() {
    //checks if there is an element next in the list
        return this.temp != null;
    }
    public Object next() {
    //gets the next element in the list
        Object returndata = this.temp.getData();
        temp = temp.getNext();
        return  returndata;
    }
    public void remove() {
    //not implemented
    }
}
}

public class Mynode {
private String data;
private Mynode next;
public Mynode (String d, Mynode n){
    this.data = d;
    this.next =n;
}
public String getData(){
    return this.data;
}
public void setNext(Mynode n){
    this.next = n;
}
public Mynode getNext(){
    return this.next;
}

}

Answer 1

Отладка может быть проще, если нам также будет дан класс Mynode.

Из информации, которую мы сейчас предоставляем, кажется, что метод split будет выглядеть бесконечно.

Метод getNext в LinkedList не должен ничего менять в текущем объекте, он должен быть просто получателем для следующего узла в списке.Поскольку вы вызываете getNext, но не сохраняете Mynode, который возвращается каким-либо образом, метод getNext будет возвращать один и тот же узел, поскольку tempFast и tempSlow никогда не ссылаются на следующий Mynode в списке.

Вместо кода здесь:

    while(tempslow.getNext()!=null && tempslow.getNext()!=null){
        tempFast.getNext();
        tempFast.getNext();
        tempslow.getNext();
    }

Я бы порекомендовал установить переменные tempFast и tempSlow для следующего узла в списке, например так:

    while(tempslow.getNext()!=null && tempslow.getNext()!=null){
        tempFast = tempFast.getNext();
        if(tempFast != null){
            tempFast = tempFast.getNext();
        }
        tempSlow = tempslow.getNext();
    }