按字母顺序对链表进行排序

Question

我有一项任务，我必须制作一个链表，其中包含一个人的姓名和他们进入大院的车牌号。但我需要使用车牌号（例如：ABS1234）按字母顺序对列表进行排序。我一直在做一些关于排序的研究，例如合并排序或使用 collection.sort，但我无法理解它。如果我能得到一些关于如何做到这一点的推动，那就太棒了。提前致谢。

public class Node {
//data fields
public String regPlate; // Registration Plate
public String firstName;
public String lastName;

//refrence link
public Node link;

//default constructor
public Node()
{
    regPlate = "";
    firstName = "";
    lastName = "";
}//end of constructor.

}//end of node class

这是我创建的节点 class。

public class LinkedList {

Node head;
Node tail;
Node current;
int listLength;
Scanner input = new Scanner(System.in);

//default constructor
public LinkedList () 
{
    head = null;
    listLength = 0;
}

//inserting new node in the beginning of the list
public void insertFirst(String fN, String lN, String rP)
{

    Node newNode = new Node();
    newNode.firstName = fN;
    newNode.lastName = lN;
    newNode.regPlate = rP;

    //make newNode point to the first node in the life
    newNode.link = head;

    //makes head point to the new first node
    head = newNode;

    if(head == null)
        tail = newNode;

    ++listLength;
}//end of insertFirst


public void displayDataLog()
{
    Node current;

    current = head;

    while(current != null)
    {
        System.out.print("\n FullName: " + current.firstName + " " + current.lastName +
                        "\n Registration Plate Number: " + current.regPlate);

        current = current.link;
    }

}//end of display vehicles

public void totalVehicles()
{
    System.out.print("\n Total Vehicle on the campus: " + listLength);
}//end of total vehicles


}//end of linked list

Answer 1

使用 Collection.sort() 这应该相当容易。

首先，您需要创建自己的 Comparator，因为默认的不起作用（您要按特定字段、车牌进行排序）。

class NodeComparator implements Comparator<Node> {
    @Override
    public int compare(Node n1, Node n2) {
        return n1.regPlate.compareTo(n2.regPlate);
    }
}

现在你有了比较器，只需使用它，这是我使用的示例（创建一个 ArrayList 并在其中引入列表的每个元素）：

private static LinkedList sortList(LinkedList list) {
    // I use an ArrayList so I can just use Collections.sort
    LinkedList sortedList = new LinkedList();
    Node current = list.head;
    ArrayList<Node> array = new ArrayList<Node>();

    while (current != null) {
        array.add(current);
        current = current.link;
    }
    array.sort(new NodeComparator());

    for (int i = array.size()-1; i >= 0; i--) {
        sortedList.insertFirst(array.get(i));
    }

    return sortedList;
}

我做了一些更改，很可能很容易适应您自己的程序。您可以在此处查看完整的工作程序：https://code.sololearn.com/cgzN5sQOI8uW.

整个代码，为了完成（以防万一 link 停止工作）：

import java.util.*; 
import java.lang.*; 
import java.io.*;

class Playground {
    public static void main(String[ ] args) {
        LinkedList list = new LinkedList();
        list.insertFirst("Robert", "Rodriguez", "RB123");
        list.insertFirst("Andrew", "Andrews", "AB123");
        list.insertFirst("Thomas", "Thomson", "TB123");

        System.out.println(list); // Prints unordered list, opposite order as they were introduced, since they were introduced from the beggining of the list.

        LinkedList sorted = sortList(list);
        System.out.println("\n"+sorted);
    }

    private static LinkedList sortList(LinkedList list) {
        // I use an ArrayList so I can just use Collections.sort
        LinkedList sortedList = new LinkedList();
        Node current = list.head;
        ArrayList<Node> array = new ArrayList<Node>();

        while (current != null) {
            array.add(current);
            current = current.link;
        }
        System.out.println("\nTemp Array:");
        System.out.println(array);

        array.sort(new NodeComparator());

        System.out.println("\nTemp Array (now sorted):");
        System.out.println(array);

        for (int i = array.size()-1; i >= 0; i--) {
            sortedList.insertFirst(array.get(i));
        }

        return sortedList;
    }
}

class NodeComparator implements Comparator<Node> {
    @Override
    public int compare(Node n1, Node n2) {
        return n1.regPlate.compareTo(n2.regPlate);
    }
}

class Node {
    //data fields
    public String regPlate; // Registration Plate
    public String firstName;
    public String lastName;

    //refrence link
    public Node link;

    //default constructor
    public Node()
    {
        regPlate = "";
        firstName = "";
        lastName = "";
    }//end of constructor.

    public String toString() {
        return this.regPlate;
    }



}//end of node class

class LinkedList {

    Node head;
    Node tail;
    Node current;
    int listLength;

    //default constructor
    public LinkedList () 
    {
        head = null;
        listLength = 0;
    }

    //inserting new node in the beginning of the list
    public void insertFirst(String fN, String lN, String rP)
    {

        Node newNode = new Node();
        newNode.firstName = fN;
        newNode.lastName = lN;
        newNode.regPlate = rP;

        insertFirst(newNode);
    }//end of insertFirst

    public void insertFirst(Node newNode) {
        //make newNode point to the first node in the life
        newNode.link = head;

        //makes head point to the new first node
        head = newNode;

        if(head.link == null)
            tail = newNode;

        ++listLength;
    }

    public void displayDataLog()
    {
        Node current;

        current = head;

        while(current != null)
        {
            System.out.print("\n FullName: " + current.firstName + " " + current.lastName +
                            "\n Registration Plate Number: " + current.regPlate);

            current = current.link;
        }

    }//end of display vehicles

    public void totalVehicles()
    {
        System.out.print("\n Total Vehicle on the campus: " + listLength);
    }//end of total vehicles

    public String toString() {
        String str = "List:\nhead -> [ ";
        Node current = head;

        while (current != null) {
            str = str + current + (current == tail ? " ] <- tail" : ", ");
            current = current.link;
        }

        return str;
    }

}//end of linked list

按字母顺序对链表进行排序

Sorting a Linked List in alphabetical order

java

sorting

singly-linked-list