java - 如何对链表进行排序？

Question

我试了一下午了。 我什至开始审视自己的智商。 这很容易，但我真的不知道该怎么做。 请帮助我，非常非常感谢! 使用java实现链表并按字母顺序排序

public class SinglyLinkedList {
private static final int DEFAULT_MAXIMUM = 10;
private SLLNode[] listArray;
private int first = 0; // first element of the list in the array.
private int firstFree = 0; // first free location in the array.

public static void main(String[] args) {
    SinglyLinkedList elementList = new SinglyLinkedList();
    elementList.insert("Hydrogen");
    elementList.insert("Boron");
    elementList.insert("Beryllium");
    elementList.insert("Helium");
    elementList.insert("Lithium");
    elementList.insert("Carbons");

    System.out.println(elementList);
}

public SinglyLinkedList() {
    listArray = new SLLNode[DEFAULT_MAXIMUM];
}

public SinglyLinkedList(int size) {
    listArray = new SLLNode[size];
}

public void insert(String data) {
    inserts(data);
}

private void inserts(String data) {
    SLLNode tempNode = new SLLNode(data);
    listArray[firstFree] = tempNode;
    firstFree++;

    order();
}

private void order() {
    int i = 0;
    /*
     * for (i = 0; i < firstFree - 1; i++) { if(listArray[i].getNext()==-1) {
     * if(listArray[i].comparaTo(listArray[firstFree-1])<0)
     * listArray[firstFree-1].setNext(i); else { i++; if (listArray[firstFree -
     * 1].comparaTo(listArray[i]) > 0 && listArray[firstFree -
     * 1].comparaTo(listArray[listArray[i].getNext()]) < 0) {
     * listArray[i].setNext(firstFree - 1); listArray[firstFree -
     * 1].setNext(listArray[i].getNext()); } else listArray[firstFree -
     * 1].setNext(i); }
     * 
     * } else if (listArray[firstFree - 1].comparaTo(listArray[i]) > 0 &&
     * listArray[firstFree - 1].comparaTo(listArray[listArray[i].getNext()]) < 0) {
     * listArray[i].setNext(firstFree - 1); listArray[firstFree -
     * 1].setNext(listArray[i].getNext()); } else listArray[firstFree -
     * 1].setNext(i); }
     */
    for (i = 0; i < firstFree - 1; i++) {
        if (listArray[i].comparaTo(listArray[first]) < 0)
            first = i;
    }
    SLLNode tempNode = new SLLNode(listArray[first].getData());
    tempNode = listArray[first];
    /*
     * System.out.println("lala"); if(firstFree==1) listArray[first].setNext(0);
     * System.out.println("lala");
     */
    int j = 0;
    if(firstFree==1)
        tempNode.setNext(0);
    if(firstFree==2) {
        listArray[0].setNext(0);
        listArray[1].setNext(1);
    }
    while (tempNode.getNext()!=-1) {
        if (listArray[firstFree - 1].comparaTo(tempNode) > 0
                && listArray[firstFree - 1].comparaTo(listArray[tempNode.getNext()]) < 0) {
            listArray[firstFree - 1].setNext(tempNode.getNext() - 1);
            tempNode.setNext(firstFree-1);
        } else {
            tempNode = listArray[tempNode.getNext()];
        }

    }
    System.out.println("lala");
}

public String toString() {
    StringBuilder tempString = new StringBuilder();
    tempString.append("first = " + first + "\n" + "firstFree = " + firstFree + "\n\n");
    for (int i = 0; i < firstFree; i++) {
        if (listArray[i] != null)
            tempString.append(i + ": " + listArray[i].getData() + "\t" + listArray[i].getNext() + "\n");
    }
    return tempString.toString();
}

/*
 * public SLLIterator getIterator() {
 * 
 * }
 */

private static class SLLNode {
    private String data;
    private int next = -1;

    public SLLNode(String data) {
        this.data = data;
    }

    public SLLNode(String data, int next) {
        this.data = data;
        this.next = next;
    }

    public void setData(String data) {
        this.data = data;
    }

    public String getData() {
        return this.data;
    }

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

    public int getNext() {
        return this.next;
    }

    public String toString() {
        return "loading";
    }

    public int comparaTo(SLLNode tempNode) {
        if (data.compareTo(tempNode.getData()) > 0)
            return 1;
        else if (data.compareTo(tempNode.getData()) < 0)
            return -1;
        else
            return 0;
    }
}}

主要问题是 while 循环和 nullPointerException 不知道如何判断是否是列表末尾

Answer 1

您需要将其分成小部分:

1. 找到新节点应该位于的节点(我们称之为before)
2. 找到此后的现有节点 - 它是 before.next - 将其称为 after。可能没有 after，在这种情况下，before.next 将为 null。
3. 使新节点的next指向after，或者为null
4. 使 before.next 指向新节点

重要的是要了解哪些变量可以为 null，以及它们的含义:

• firstNode 可以为 null。这意味着它是一个空列表
• 节点的next 可以为空。这意味着它是列表中的最后一个元素。

您的代码必须处理这两个问题。

一次拿这些。第一个可能是最困难的，因为其他都非常简单。

链表不会将其元素存储在数组中，并且没有最大大小。 LinkedList 需要的唯一字段是 Node firstNode。要访问其他元素，请点击第一个元素的 next 链接。所以:

 Node findInsertionPoint(String data) {
     Node node = this.firstNode;
     if(node == null) {
         return null;
     }
     Node nextNode = node.getNext();
     while(nextNode != null && nextNode.getData().compareWith(data) <=0) {
          node = nextNode;
          nextNode = node.getNext();
     }
     return node;
 }

这将返回:

• null 表示空列表(当 firstNode 为 null 时)
• 节点在其之后您的新节点应该位于 - 即在其他情况下所需的之前。

findInsertionPoint() 本身就是一个可测试的方法，因此在继续之前对其进行测试并确保它适用于多种情况。一个空列表。单元素列表。新节点应该先行。新节点应该放在最后。新节点位于中间。

现在您只需创建新节点，并在新节点和 before 节点上使用正确的值调用 setNext() 即可。如果没有 before 节点，则需要设置 this.firstNode 指向新节点。

<小时/>

请注意，这里您不是对链接列表进行排序 - 您是将一个元素插入到已排序列表中的正确位置。对链表进行排序的一种方法是逐一取出其元素并将它们插入到新列表中。但还有其他更有效的方法，您可能会在以后的学习中遇到。