Ex2_2_17链表归并排序

  1. public class List<Item> {
  2.     private class Node{
  3.         Item item;
  4.         Node next;
  5.     }
  7.     private Node head;
  8.     private Node tail;
  10.     private boolean less(Comparable v, Comparable w){ return v.compareTo(w)<0 ;}
  11.     private boolean isEmpty(){ return head == null;}
  12.     private void add(Item item){
  13.         Node current = tail;
  14.         tail = new Node();
  15.         tail.item = item;
  16.         if(isEmpty()) head = tail;
  17.         else current.next = tail;
  18.     }
  20.     private Node ListMerge(Node head){
  21.         if(head.next == null) return head;
  22.         Node fast = head.next;
  23.         Node slow = head;
  24.         while (fast != null && fast.next != null){
  25.             fast = fast.next.next;
  26.             slow = slow.next;
  27.         }//slow-fast方法找到中间节点,fast走两步,slow走一步,当fast到末尾,slow即在中间节点
  28.         Node leftHead = head;
  29.         Node rightHead = slow.next;
  30.         slow.next = null;//左边去尾
  31.         Node newLeft = ListMerge(leftHead);
  32.         Node newRight = ListMerge(rightHead);
  34.         Node newList;//newList用来指向归并后数组头结点
  35.         Node tail;//tail指向归并中的尾节点
  38.         if(less((String)newLeft.item,(String)newRight.item)){
  39.             newList = newLeft;
  40.             newLeft = newLeft.next;
  41.         }else{
  42.             newList = newRight;
  43.             newRight = newRight.next;
  44.         }//确定头结点
  47.         tail = newList;
  48.         tail.next = null;
  50.         //升序归并尾节点
  51.         while (newLeft != null || newRight !=null){
  52.             if(newLeft == null){
  53.                 tail.next = newRight;
  54.                 newRight = null;
  55.             }
  56.             else if(newRight == null){
  57.                 tail.next = newLeft;
  58.                 newLeft = null;
  59.             }
  60.             else if(less((String)newLeft.item,(String)newRight.item)){
  61.                 tail.next = newLeft;
  62.                 newLeft = newLeft.next;
  63.                 tail = tail.next;
  64.                 tail.next = null;
  65.             }
  66.             else{
  67.                 tail.next = newRight;
  68.                 newRight = newRight.next;
  69.                 tail = tail.next;
  70.                 tail.next = null;
  71.             }
  72.         }
  73.         //返回归并后数组头结点
  74.         return newList;
  75.     }
  77.     public static void main(String[] args){
  78.         List<String> list = new List<>();
  79.         for(int i = 5; i >= 0; i--){
  80.             list.add(Integer.toString(i));
  81.         }
  83.         List.Node temp = list.ListMerge(list.head);
  84.     }
  85. }

要点:

  1. 关于链表如何找到中间节点:使用fast-slow方法,fast节点初始为head.next,slow节点初始为head,每次fast后移两节点,slow后移一节点,当fast到末尾时,slow就在中间节点.比使用一个int变量标记循环要简单的多
  1. Node fast = head.next;
  2.         Node slow = head;
  3.         while (fast != null && fast.next != null){
  4.             fast = fast.next.next;
  5.             slow = slow.next;
  6.         }//slow-fast方法找到中间节点,fast走两步,slow走一步,当fast到末尾,slow即在中间节点
  1. 记得分成左右部分后,左边链表的尾节点.next要赋值为null,否则最终的链表会无限循环
  1. slow.next = null;//左边去尾
  1. newList节点和tail节点分别标识排序后链表的头和尾
  1. Node newList;//newList用来指向归并后数组头结点
  2.     Node tail;//tail指向归并中的尾节点

特点:

  1. 这是链表排序的最佳方法,因为不需要额外空间且运行时间是线性的.

Review:

  1. 链表归并排序只是List类下的方法,不要和其他排序算法实现静态方法搞混,此处都为非静态方法;
  2. 对于链表的归并,一个ListMerge函数既做到排序有完成归并,无需sort()函数;
  3. 对于(newLeft == null)和(newRight == null),直接tail.next = newRight和tail.next = newLeft整个半条链表就会连接,不用一个个节点连接;
  4. 关于newList和tail指针的必要性:之所以分设两个指针,newList为了始终执行归并后链表的头结点,如果只有一个指针,最终无法返回头结点,所以tail起到时刻跟踪尾部节点功能;
  1. tail.next = newRight;//1
  2.     newRight = newRight.next;//2
  3.     tail = tail.next;//3
  4.     tail.next = null;//4
  1. tail语句顺序问题:如上为最后的while循环,2一定要在3,4前,tail相当于一个遥控器,3,4先执行会使其和newRight遥控器对应一个,这样tail.next也就是newRight.next = null,内存中后面的Node直接变成无引用,语句4可有可无,tail.next总会被覆盖;