Verkettete Listen-Verkettung

Arbeiten beim erstellen von verknüpften Listen für eine Aufgabe und eine Voraussetzung ist eine Methode mit dem Namen concat, die eine Liste der parameter und fügt es an das Ende der aktuellen Liste. Es ist nicht notwendig für diese Methode, Rekursion zu verwenden, aber unsere Programme werden sollen, Rekursion zu verwenden, stark. Ich Frage mich nur, ob es überhaupt möglich ist zu kommen mit einem rekursiven Algorithmus. Unsere Liste Klassen haben nur einen head-Knoten, sonst nichts, und Sie sind nicht doppelt verknüpft.

Meinem aktuellen Versuch kann nur anfügen, der erste Wert rekursiv. Ich weiß, was es tut falsch ist, aber ich kann nicht kommen mit einer Lösung. Die erste Methode ist, was heißt eigentlich auf einer Liste, die eine Liste weitergegeben werden zu "verketten". Ich habe dann versucht den Schwanz der Liste, und übergeben Sie diese in der rekursiven Methode. Diese "wrapper" - Methode ist eine zwingende Voraussetzung für unsere rekursive Methoden. Hier ist mein Versuch, aber es ist offensichtlich versagt, da bin ich mit Mühe voran die node-Referenz "pt", um den nächsten Knoten in der Liste einmal alle Anrufe pop aus dem Stapel entfernt werden und dann erneut die Eingabe der rekursiven Aufrufe concat. Wenn diese ist möglich mit Rekursion, können Sie bitte geben Sie mir eine Idee, wie man Voraus, dieser Wert Sie in der ersten Liste, und geben Sie die rekursiven Aufrufe oder vielleicht auch nur einen besseren Allgemeinen Ansatz für dieses problem? Vielen Dank für Ihre Zeit.

public void concat(MyString list1) {
    CharacterNode tail = null, pt = list1.head;
    //Find the tail of the list
    if (pt == null) {
    } else if (pt.getNext() == null) {
        tail = pt;
    } else {
        while (pt.getNext() != null) {
            pt = pt.getNext();
        }
        tail = pt;
    }
    list1.head = concat(list1.head, tail, list1.head);
}
private static CharacterNode concat(CharacterNode lhead, CharacterNode tail, CharacterNode pt) {
    //Pass in smaller list every time
    //Head traverses down list till the end
    //Add new node with (pt's letter, null link)
    if (lhead == null) {
    //If head is null, we need to add the node
        lhead = new CharacterNode(pt.getCharacter(),null);
    } else if (tail.getNext() == lhead) {
    //If the head is past tail, stop   
    } else {
        //Call concat on a smaller list
        lhead.setNext(concat(lhead.getNext(),tail,pt));
    }
    return lhead;
}

Hier CharacterNode:

class CharacterNode {
    private char letter;
    private CharacterNode next;

    public CharacterNode(char ch, CharacterNode link) {
        letter = ch;
        next = link;
    }

    public void setCharacter(char ch) {
        this.letter = ch;
    }

    public char getCharacter() {
        return letter;
    }

    public void setNext(CharacterNode next) {
        this.next = next;
    }

    public CharacterNode getNext() {
        return next;
    }
}

MyString:

class MyString {
    //member variable pointing to the head of the linked list
    private CharacterNode head;

    //default constructor
    public MyString() {
    }

    //copy constructor
    public MyString(MyString l) {
    }

    //constructor from a String
    public MyString(String s) {
    }

    //for output purposes -- override Object version
    //no spaces between the characters, no line feeds/returns
    public String toString() {
    }

    //create a new node and add it to the head of the list
    public void addHead(char ch) {
    }

    //create a new node and add it to the tail of the list -- "wrapper"
    public void addTail(char ch) {
    }

    //Recursive method for addTail
    private static CharacterNode addTail(CharacterNode L, char letter) {
    }

    //modify the list so it is reversed
    public void reverse() {
    }

    //remove all occurrences of the character from the list -- "wrapper"
    public void removeChar(char ch) {
    }

    //Recursive removeChar method
    private static CharacterNode removeChar(CharacterNode n, char letter) {
    }

    //"wrapper" for recursive length()
    public int length() {
    }

    //Returns the length of the linked list
    private static int length(CharacterNode L) {
    }

    //concatenate a copy of list1 to the end of the list
    public void concat(MyString list1) {
    }

    //recursive method for concat
    private static CharacterNode concat(CharacterNode lhead, CharacterNode tail, CharacterNode pt) {
    }
}

InformationsquelleAutor stevenelberger | 2013-03-16