Мне нужно отсортировать связанный список по алфавиту. У меня есть объединенный список с именами пассажиров и вам нужно, чтобы имя пассажиров сортировалось в алфавитном порядке. Как это сделать? У кого-нибудь есть ссылки или видео?
Java как сортировать Связанный список?
Ответ 1
Вы можете использовать Collections#sort
для сортировки в алфавитном порядке.
Ответ 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)
, это обычно довольно удобно.
Ответ 3
В java8 вам больше не нужно использовать метод Collections.sort, поскольку LinkedList наследует метод сортировки из java.util.List, поэтому адаптируя Fido к 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
Ответ 4
Вот пример сортировки реализованного связанного списка в java без использования стандартных java-библиотек.
package SelFrDemo;
class NodeeSort {
Object value;
NodeeSort next;
NodeeSort(Object val) {
value = val;
next = null;
}
public Object getValue() {
return value;
}
public void setValue(Object value) {
this.value = value;
}
public NodeeSort getNext() {
return next;
}
public void setNext(NodeeSort next) {
this.next = next;
}
}
public class SortLinkList {
NodeeSort head;
int size = 0;
NodeeSort add(Object val) {
// TODO Auto-generated method stub
if (head == null) {
NodeeSort nodee = new NodeeSort(val);
head = nodee;
size++;
return head;
}
NodeeSort temp = head;
while (temp.next != null) {
temp = temp.next;
}
NodeeSort newNode = new NodeeSort(val);
temp.setNext(newNode);
newNode.setNext(null);
size++;
return head;
}
NodeeSort sort(NodeeSort nodeSort) {
for (int i = size - 1; i >= 1; i--) {
NodeeSort finalval = nodeSort;
NodeeSort tempNode = nodeSort;
for (int j = 0; j < i; j++) {
int val1 = (int) nodeSort.value;
NodeeSort nextnode = nodeSort.next;
int val2 = (int) nextnode.value;
if (val1 > val2) {
if (nodeSort.next.next != null) {
NodeeSort CurrentNext = nodeSort.next.next;
nextnode.next = nodeSort;
nextnode.next.next = CurrentNext;
if (j == 0) {
finalval = nextnode;
} else
nodeSort = nextnode;
for (int l = 1; l < j; l++) {
tempNode = tempNode.next;
}
if (j != 0) {
tempNode.next = nextnode;
nodeSort = tempNode;
}
} else if (nodeSort.next.next == null) {
nextnode.next = nodeSort;
nextnode.next.next = null;
for (int l = 1; l < j; l++) {
tempNode = tempNode.next;
}
tempNode.next = nextnode;
nextnode = tempNode;
nodeSort = tempNode;
}
} else
nodeSort = tempNode;
nodeSort = finalval;
tempNode = nodeSort;
for (int k = 0; k <= j && j < i - 1; k++) {
nodeSort = nodeSort.next;
}
}
}
return nodeSort;
}
public static void main(String[] args) {
SortLinkList objsort = new SortLinkList();
NodeeSort nl1 = objsort.add(9);
NodeeSort nl2 = objsort.add(71);
NodeeSort nl3 = objsort.add(6);
NodeeSort nl4 = objsort.add(81);
NodeeSort nl5 = objsort.add(2);
NodeeSort NodeSort = nl5;
NodeeSort finalsort = objsort.sort(NodeSort);
while (finalsort != null) {
System.out.println(finalsort.getValue());
finalsort = finalsort.getNext();
}
}
}
Ответ 5
Я бы не стал. Я бы использовал ArrayList или отсортированную коллекцию с помощью Comparator. Сортировка LinkedList - это самая неэффективная процедура, о которой я могу думать.
Ответ 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;
}
Ответ 7
Элегантное решение с 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));
Ответ 8
Если вы хотите знать, как сортировать связанный список, не используя стандартные библиотеки Java, я бы предложил посмотреть на различные алгоритмы самостоятельно. Примеры здесь показывают, как реализовать сортировку вставки, другое сообщение StackOverflow показывает тип слияния, и ehow даже дает некоторые примеры того, как создать пользовательскую функцию сравнения, если вы хотите дополнительно настроить свой вид.