1 import java.util.Iterator;  2 /  3  * 对单向链表的由小到大归并排序  4  * @author evasean www.cnblogs.com/evasean/  5  * @param <T>  6 */  7 public class MergeSortLinkedList <T extends Comparable<T>> implements Iterable<T>{  8 private Node first = null;  9 private Node last = null;  10 private int n;  11 private class Node{  12  T element;  13  Node next;  14  }  15 private boolean less(Comparable v, Comparable w) {  16 return v.compareTo(w) < 0;  17  }  18  @Override  19 public Iterator<T> iterator() {  20 // TODO Auto-generated method stub  21 return new ListIterator();  22  }  23 private class ListIterator implements Iterator<T>{  24 private Node current = first;  25  @Override  26 public boolean hasNext() {  27 // TODO Auto-generated method stub  28 return current != null;  29  }  30  31  @Override  32 public T next() {  33 // TODO Auto-generated method stub  34 T t = current.element;  35 current = current.next;  36 return t;  37  }  38  }  39 public void add(T t){  40 Node node = new Node();  41 node.element = t;  42 node.next = null;  43 if(first == null && last == null){  44 first = node;  45 last = node;  46 }else if(first != null && first == last){  47 first.next = node;  48 last = node;  49 }else{  50 last.next = node;  51 last = node;  52  }  53 n++;  54  }  55  @Override  56 public String toString(){  57 Iterator<T> iter = iterator();  58 String ret = iter.next().toString();  59 while(iter.hasNext()){  60 ret += “, “+ iter.next().toString() ;  61  }  62 return ret;
 

 63  }  64 public void mergeSort(){  65 first = sort(first);  66  }  67
  68 private Node sort(Node head){  69 if(head == null || head.next == null) return head;  70 Node slow = head;  71 Node fast = head;  72 //取中间节点  73 while(fast.next != null && fast.next.next != null){  74 slow = slow.next;  75 fast = fast.next.next;  76  }  77 Node left = head;  78 Node right = slow.next;  79 slow.next = null; //将左右链表分开  80 left = sort(left);  81 right = sort(right);  82 return merge(left,right);  83  }  84 private Node merge(Node left, Node right){  85 //System.out.println(“left=”+left.element+“,right=”+right.element);  86 Node aux = new Node(); //需要耗费logn的额外空间  87 Node l= left;  88 Node r = right;  89 Node current = aux;  90 while(l != null && r!=null){  91 if(less(r.element,l.element)) {  92 current.next = r;  93 current = current.next;  94 r = r.next;  95  }  96 else {  97 current.next = l;  98 current = current.next;  99 l= l.next; 100  } 101  } 102 if(l!=null) current.next = l; // 如果左侧没遍历完，将其连接至current后 103 else if(r != null) current.next = r; //如果右侧没遍历完，将其连接至current后 104 return aux.next; //返回归并好的链表 105  } 106 public static void main(String[] args){ 107 ShuffleLinkedList<Integer> sll = new ShuffleLinkedList<Integer>(); 108 sll.add(1); 109 sll.add(2); 110 sll.add(11); 111 sll.add(9); 112 sll.add(10); 113 sll.add(4); 114 sll.add(7); 115  System.out.println(sll); 116  sll.mergeSort(); 117  System.out.println(sll); 118  } 119 120 } 

讯享网