В двусвязном списке, как отсортировать узлы в порядке возрастания по назначенному ключу?

Question

Я должен сортировать узлы в двусвязном списке в порядке возрастания по ключу. Я не могу использовать коллекции в этом методе. Список модульных тестов выглядит следующим образом:

гл: 58, ci: 41, ах: 13, ах: 63, ai: 9, id: 70, ah: 32, id: 92

Желаемый результат:

ах: 13, ах: 63, ах: 32, аи: 9, ци: 41, гл: 58, id: 70, id : 92

Но выходит как:

NullPointerException: LinkedList.swapIfNeeded (LinkedList. java: 144), LinkedList.sort (LinkedList. java) : 163)

Я работал над этим часами, и это последний метод, который мне нужен, чтобы закончить sh задание. Каждый другой метод в классе прошел модульные тесты, поэтому я не знаю, что я делаю неправильно. Вот мой класс с методом sort () внизу. Извиняюсь, если вопрос имеет неправильное форматирование, я новичок в этом.

public class LinkedList {
public static class Node{
    String key;
    int value;
    Node next;
    Node prev;

    public Node(String key, int value) {
        this.key = key;
        this.value = value;
    }

    public Node getNext() {
        return next;
    }

    public Node getPrev() {
        return prev;
    }

    public String getKey() {
        return key;
    }

    public int getValue() {
        return value;
    }
}

private Node head;
private Node tail;

public LinkedList() {
    head = null;
    tail = null;
}

public Node getHead() {
    return head;
}

public Node getTail() {
    return tail;
}

public void addHead(String key, int val) {
    Node n = new Node(key, val);

    if(head == null) {
        head = n;
        tail = n;
    } else {
        head.prev = n;
        n.next = head;
        head = n;
    }
}

public void addTail(String key, int val) {
    Node n = new Node(key, val);

    if(tail == null) {
        head = n;
        tail = n;
    } else {
        tail.next = n;
        n.prev = tail;
        tail = n;
    }
}

public String toString() {
    String ret = "";

    Node curr = head;

    while(curr != null) {
        if(curr.next != null)
            ret += curr.key + ":" + curr.value + ", ";
        else
            ret += curr.key + ":" + curr.value;

        curr = curr.next;
    }

    return ret;
}

public Node find(String key) {
    Node curr = head;

    while(curr != null) {
        if(curr.key.equals(key))
            return curr;

        curr = curr.next;
    }

    return null;
}


//////////////////////// YOUR CODE HERE ////////////////////////

public void unlinkNode(Node n) {

    Node sucNode = n.next;
    Node prevNode = n.prev;

    if (sucNode != null) {
        sucNode.prev = prevNode;
    }

    if (prevNode != null) {
        prevNode.next = sucNode;
    }

    if (n == head) {
        head = sucNode;
    }

    if (n == tail) {
        tail = prevNode;
    }
}

public void addAfter(Node n, Node before) {

    n.next = before.next;

    before.next = n;

}

public boolean swapIfNeeded(Node n) {

    Node newNode = n.next;

    if (n == tail) {
        return false;
    }

    if (n.getKey().compareTo(newNode.getKey()) > 0) {
        unlinkNode(n);

        addAfter(n, newNode);

        return true;
    }
    return false;
}

public void sort() {

    boolean done = false;

    while (!done) {
        Node cur = head;
        done = true;

        while (cur != null) {
            if (swapIfNeeded(cur)) {
                swapIfNeeded(cur);
                done = false;
            }

            cur = cur.getNext();
        }
    }




}






///////////////////////////////////////////////////////////////

} ​​