有序鍊錶：
按關鍵值排序。刪除鏈頭時，就刪除最小(/最大)的值，插入時，搜索插入的位置。
插入時需要比較O(N)，平均O(N/2)，刪除最小(/最大)的在鏈頭的數據時效率為O(1),
如果一個應用需要頻繁的存取(插入/查找/刪除)最小(/最大)的數據項，那麼有序鍊錶是一個不錯的選擇優先級隊列可以使用有序鍊錶來實現有序鍊錶的插入排序：
對一個無序數組，用有序鍊錶來排序，比較的時間級還是O(N^2)
複製時間級為O(2*N)，因為複制的次數較少，第一次放進鍊錶數據移動N次，再從鍊錶複製到數組，又是N次每插入一個新的鏈結點，不需要復制移動數據，只需要改變一兩個鏈結點的鏈域
import java.util.Arrays; import java.util.Random; /** * 有序鍊錶對數組進行插入排序* @author stone */ public class LinkedListInsertSort<T extends Comparable<T>> { private Link<T> first; //首結點public LinkedListInsertSort() { } public boolean isEmpty() { return first == null; } public void sortList(T[] ary) { if (ary == null) { return; } //將數組元素插入進鍊錶,以有序鍊錶進行排序for (T data : ary) { insert(data); } // } public void insert(T data) {// 插入到鏈頭, 以從小到大排序Link<T> newLink = new Link<T>(data); Link<T> current = first, previous = null; while (current != null && data.compareTo(current.data) > 0) { previous = current; current = current.next; } if (previous == null) { first = newLink; } else { previous.next = newLink; } newLink.next = current; } public Link<T> deleteFirst() {//刪除鏈頭Link<T> temp = first; first = first.next; //變更首結點，為下一結點return temp; } public Link<T> find(T t) { Link<T> find = first; while (find != null) { if (!find.data.equals(t)) { find = find.next; } else { break; } } return find; } public Link<T> delete(T t) { if (isEmpty()) { return null; } else { if (first.data.equals(t)) { Link<T> temp = first; first = first.next; //變更首結點，為下一結點return temp; } } Link<T> p = first; Link<T> q = first; while (!p.data.equals(t)) { if (p.next == null) {//表示到鏈尾還沒找到return null; } else { q = p; p = p.next; } } q.next = p.next; return p; } public void displayList() {//遍歷System.out.println("List (first-->last):"); Link<T> current = first; while (current != null) { current.displayLink(); current = current.next; } } public void displayListReverse() {//反序遍歷Link<T> p = first, q = first.next, t; while (q != null) {//指針反向，遍歷的數據順序向後t = q.next; //no3 if (p == first) {// 當為原來的頭時，頭的.next應該置空p.next = null; } q.next = p;// no3 -> no1 pointer reverse p = q; //start is reverse q = t; //no3 start } //上面循環中的if裡，把first.next 置空了, 而當q為null不執行循環時，p就為原來的最且一個數據項，反轉後把p賦給first first = p; displayList(); } class Link<T> {//鏈結點T data; //數據域Link<T> next; //後繼指針，結點鏈域Link(T data) { this.data = data; } void displayLink() { System.out.println("the data is " + data.toString()); } } public static void main(String[] args) { LinkedListInsertSort<Integer> list = new LinkedListInsertSort<Integer>(); Random random = new Random(); int len = 5; Integer[] ary = new Integer[len]; for (int i = 0; i < len; i++) { ary[i] = random.nextInt(1000); } System.out.println("----排序前----"); System.out.println(Arrays.toString(ary)); System.out.println("----鍊錶排序後----"); list.sortList(ary); list.displayList(); } }
列印
----排序前---- [595, 725, 310, 702, 444] ----鍊錶排序後---- List (first-->last): the data is 310 the data is 444 the data is 595 the data is 702 the data is 725
單鍊錶反序:
public class SingleLinkedListReverse { public static void main(String[] args) { Node head = new Node(0); Node temp = null; Node cur = null; for (int i = 1; i <= 10; i++) { temp = new Node(i); if (i == 1) { head.setNext(temp); } else { cur.setNext(temp); } cur = temp; }//10.next = null; Node h = head; while (h != null) { System.out.print(h.getData() + "/t"); h = h.getNext(); } System.out.println(); //反轉1 // h = Node.reverse1(head); // while (h != null) { // System.out.print(h.getData() + "/t"); // h = h.getNext(); // } //反轉2 h = Node.reverse1(head); while (h != null) { System.out.print(h.getData() + "/t"); h = h.getNext(); } } } /* * 單鍊錶的每個節點都含有指向下一個節點屬性*/ class Node { Object data;//數據對象Node next; //下一節點Node(Object d) { this.data = d; } Node(Object d, Node n) { this.data = d; this.next = n; } public Object getData() { return data; } public void setData(Object data) { this.data = data; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } //方法1 head被重置static Node reverse1(Node head) { Node p = null; //反轉後新的頭Node q = head; //輪換結果：012,123,234,.... 10 null null while (head.next != null) { p = head.next; // 第1個換成第2個這時p表示原始序列頭中的next head.next = p.next; // 第2個換成第3個p.next = q; //已經跑到第1位置的原第2個的下一個就要變成原第1個q = p; //新的第1個要變成當前第一個} return p; } //方法2 head沒重置static Node reverse2(Node head) { //將中間節點的指針指向前一個節點之後仍然可以繼續向後遍歷鍊錶Node p1 = head, p2 = head.next, p3; // 前中後//輪換結果：012, 123, 234, 345, 456.... 9 10 null while (p2 != null) { p3 = p2.next; p2.next = p1; //指向後變指向前p1 = p2; //2、3向前挪p2 = p3; } head.next = null;//head沒變，當輸出到0時，再請求0.next 為1 return p1; } }