Java, как отсортировать связанный список?

Question

Мне нужно отсортировать связанный список по алфавиту.У меня есть связанный список полных имен пассажиров, и мне нужно отсортировать имена пассажиров в алфавитном порядке.Как можно это сделать?У кого-нибудь есть ссылки или видео?

Answer 1

Вы можете использовать Collections#sort для сортировки по алфавиту.

Answer 2

Чтобы отсортировать строки в алфавитном порядке, вам нужно будет использовать Collator, например:

 LinkedList<String> list = new LinkedList<String>();
 list.add("abc");
 list.add("Bcd");
 list.add("aAb");
 Collections.sort(list, new Comparator<String>() {
     @Override
     public int compare(String o1, String o2) {
         return Collator.getInstance().compare(o1, o2);
     }
 });

Потому что, если вы просто позвоните Collections.sort(list), у вас будут проблемы со строками, которые содержат заглавные буквы.

Например, в коде, который я вставил, после сортировки список будет: [aAb, abc, Bcd], но если вы просто позвоните Collections.sort(list);, вы получите: [Bcd, aAb, abc]

Примечание : при использовании Collator вы можете указать локаль Collator.getInstance(Locale.ENGLISH), это обычно довольно удобно.

Answer 3

В java8 вам больше не нужно использовать метод Collections.sort, так как LinkedList наследует метод sort из java.util.List, поэтому адаптирует ответ Фидо к Java8:

    LinkedList<String>list = new LinkedList<String>();
    list.add("abc");
    list.add("Bcd");
    list.add("aAb");

    list.sort( new Comparator<String>(){
    @Override
        public int compare(String o1,String o2){
            return Collator.getInstance().compare(o1,o2);
        }
    });

Рекомендации:

http://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html

http://docs.oracle.com/javase/7/docs/api/java/util/List.html

Answer 4

Элегантное решение начиная с JAVA 8:

LinkedList<String>list = new LinkedList<String>();
list.add("abc");
list.add("Bcd");
list.add("aAb");

list.sort(String::compareToIgnoreCase);

---

Другой вариант будет использовать лямбда-выражения:

list.sort((o1, o2) -> o1.compareToIgnoreCase(o2));

Answer 5

Вот пример для сортировки реализованного связанного списка в Java без использования стандартных библиотек Java.

Answer 6

Node mergeSort(Node head) {
    if(head == null || head.next == null) {
        return head;
    }

    Node middle = middleElement(head);
    Node nextofMiddle = middle.next;
    middle.next = null;

    Node left = mergeSort(head);
    Node right = mergeSort(nextofMiddle);

    Node sortdList = merge(left, right);

    return sortdList;
}

Node merge(Node left, Node right) {
    if(left == null) {
        return right;
    }

    if(right == null) {
        return left;
    }
    Node temp = null;
    if(left.data < right.data) {
        temp = left;
        temp.next = merge(left.next, right);
    } else {
        temp = right;
        temp.next = merge(left, right.next);
    }

    return temp;
}

Node middleElement(Node head) {
    Node slow = head;
    Node fast = head;
    while (fast != null && fast.next != null && fast.next.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

Answer 7

Я бы не стал. Я бы использовал ArrayList или отсортированную коллекцию с Comparator. Сортировка LinkedList - о самой неэффективной процедуре, которую я могу придумать.

Answer 8

Вы можете сделать это с помощью лямбда-выражения Java 8:

LinkedList<String> list=new LinkedList<String>();
list.add("bgh");
list.add("asd");
list.add("new");
//lambda expression
list.sort((a,b)->a.compareTo(b));

Answer 9

Если вы хотите знать, как сортировать связанный список без использования стандартных библиотек Java, я бы посоветовал взглянуть на разные алгоритмы самостоятельно.Примеры здесь показывают, как реализовать сортировку вставкой, в другом посте StackOverflow показана сортировка слиянием , а ehow даже приведены некоторые примеры создания пользовательской функции сравненияна случай, если вы захотите дополнительно настроить свой вид.