链表排序

148. 排序链表的最优方法应该是归并排序，鉴于面试时候经常会问链表快排，本文简单总结下链表排序的归并和快排方法。至于插入排序或者冒泡排序什么的，比较简单，本文不作介绍。

1. 归并排序

   • 自顶向下：采用递归方式进行归并，空间复杂度O(lg n)

     public ListNode sortList(ListNode head) {
         if(head == null || head.next == null)
             return head;
         //归并
         ListNode vir = new ListNode();
         vir.next = head;
         ListNode fast = vir, slow = vir;
         //快慢指针找中点，这里借助虚拟节点，边界处理起来容易一点
         while(fast != null && fast.next != null){
             fast = fast.next.next;
             slow = slow.next;
         }
         ListNode p1 = sortList(slow.next);
         slow.next = null;
         ListNode p2 = sortList(head);
         return merge2List(p1, p2);
     }
     //合并两个有序链表
     public ListNode merge2List(ListNode head1, ListNode head2){
         ListNode vir = new ListNode(), point = vir;
         while(head1 != null && head2 != null){
             if(head1.val < head2.val){
                 point.next = head1;
                 head1 = head1.next;
             }else{
                 point.next = head2;
                 head2 = head2.next;
             }
             point = point.next;
         }
         point.next = head1 == null ? head2 : head1;
         return vir.next;
     }

   • 自底向上：用sublength辅助，采用非递归方式进行归并，空间复杂度O(1)

     public ListNode sortList(ListNode head) {
         if(head == null || head.next == null)
             return head;
         //自底向上非递归 归并
         int length = 0;
         ListNode point = head;
         while(point != null){
             length++;
             point = point.next;
         }
         ListNode vir = new ListNode(0, head), prev = vir;
         //sublength，每次乘以2
         for(int sublength = 1; sublength < length; sublength <<= 1){
             prev = vir;
             while(prev.next != null){
                 //head1,tail1,head2,tail2分别表示要合并的两个链表的头尾节点
                 ListNode head1 = prev.next, tail1 = prev;
                 for(int i = 0; i < sublength && tail1.next != null; ++i){
                     tail1 = tail1.next;
                 }
                 ListNode head2 = tail1.next, tail2 = tail1;
                 for(int i = 0; i < sublength && tail2.next != null; ++i){
                     tail2 = tail2.next;
                 }
                 //把两个链表完全切开，然后调用merge2List
                 tail1.next = null;
                 ListNode temp = tail2.next;
                 tail2.next = null;
                 ListNode[] nodes = merge2List(head1, head2);
                 //合并好的链表再放回原链表
                 prev.next = nodes[0];
                 nodes[1].next = temp;
                 prev = nodes[1];
             }
         }
         return vir.next;
     }
     //合并两个有序链表，这里额外返回一个链表尾部
     public ListNode[] merge2List(ListNode head1, ListNode head2){
         ListNode vir = new ListNode(), point = vir;
         while(head1 != null && head2 != null){
             if(head1.val < head2.val){
                 point.next = head1;
                 head1 = head1.next;
             }else{
                 point.next = head2;
                 head2 = head2.next;
             }
             point = point.next;
         }
         point.next = head1 == null ? head2 : head1;
         while(point.next != null)
             point = point.next;
         return new ListNode[]{vir.next, point};
     }

2. 快速排序

   快排需要注意两点：

   • 递归时要同时用到head和tail，每次去除pivot节点，否则容易陷入死循环
   • 可以考虑加上随机化算法，即随机在head~tail之间选择一个节点和head交换。本文将head和中点交换。

   public ListNode sortList(ListNode head){
       if(head==null||head.next==null) return head;
       // 没有条件，创造条件。自己添加头节点，最后返回时去掉即可。
       ListNode newHead=new ListNode(-1);
       newHead.next=head;
       return quickSort(newHead,null);
   }
   // 带头结点的链表快速排序
   private ListNode quickSort(ListNode head,ListNode end){
       if (head==end||head.next==end||head.next.next==end) return head;
       randHead(head, end);
       // 将小于划分点的值存储在临时链表中
       ListNode tmpHead=new ListNode(-1);
       // partition为划分点，p为链表指针，tp为临时链表指针
       ListNode partition=head.next,p=partition,tp=tmpHead;
       // 将小于划分点的结点放到临时链表中
       while (p.next!=end){
           if (p.next.val<partition.val){
               tp.next=p.next;
               tp=tp.next;
               p.next=p.next.next;
           }else {
               p=p.next;
           }
       }
       // 合并临时链表和原链表，将原链表接到临时链表后面即可
       tp.next=head.next;
       // 将临时链表插回原链表，注意是插回！（不做这一步在对右半部分处理时就断链了）
       head.next=tmpHead.next;
       quickSort(head,partition);
       quickSort(partition,end);
       // 题目要求不带头节点，返回结果时去除
       return head.next;
   }
   private void randHead(ListNode head,ListNode end){
       int length = 0;
       ListNode slow=head, fast = head;
       while(fast != end && fast.next != end){
           slow = slow.next;
           fast = fast.next.next;
       }
       ListNode node1 = head.next, node2 = slow.next;
       head.next = node2;
       slow.next = node1;
       ListNode temp = node2.next;
       node2.next = node1.next;
       node1.next = temp;
   }

打赏