Java如何对链表进行排序？
我需要按字母顺序对链表进行排序。 我有一个链接列表，其中包含乘客姓名，并且需要按字母顺序对乘客姓名进行排序。 怎么会这样做？ 有人有任何参考或video吗？
您可以使用Collections#sort按字母顺序对事物进行排序。
为了按字母顺序对字符串进行排序，您需要使用Collator ，例如：
LinkedList list = new LinkedList (); list.add("abc"); list.add("Bcd"); list.add("aAb"); Collections.sort(list, new Comparator () { @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)这通常非常方便。
在java8中，您不再需要使用Collections.sort方法，因为LinkedList从java.util.Listinheritance了方法排序，因此使Fido的答案适应Java8：
LinkedListlist = new LinkedList (); list.add("abc"); list.add("Bcd"); list.add("aAb"); list.sort( new Comparator (){ @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
下面是在不使用任何标准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(); } } }
自JAVA 8以来的优雅解决方案：
LinkedListlist = new LinkedList (); list.add("abc"); list.add("Bcd"); list.add("aAb"); list.sort(String::compareToIgnoreCase);
另一种选择是使用lambda表达式：
list.sort((o1, o2) -> o1.compareToIgnoreCase(o2));
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; }
我不会。 我会使用ArrayList或带有Comparator的有序集合。 对LinkedList进行排序是我能想到的最低效的过程。
如果您想知道如何在不使用标准Java库的情况下对链表进行排序，我建议您自己查看不同的算法。 这里的示例显示了如何实现插入排序，另一个StackOverflowpost显示了合并排序 ，并且ehow甚至提供了一些关于如何创建自定义比较函数的示例，以防您想要进一步自定义排序。
你可以通过Java 8 lambda表达式来完成它：
LinkedList list=new LinkedList (); list.add("bgh"); list.add("asd"); list.add("new"); //lambda expression list.sort((a,b)->a.compareTo(b));