对链表进行插入排序

发布时间:2020-10-14 11:30:00
阅读量:44
作者:猎维人工智能培训
算法面试题

题目描述

在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。


示例 1:

输入: 4->2->1->3

输出: 1->2->3->4


示例 2:

输入: -1->5->3->4->0

输出: -1->0->3->4->5


分析与解法

解析一 归并排序

首先看一下归并排序,其思路是先将所有元素两两划分为一组,然后递归合并,合并就相当于将两个排序好的链表合并为一个。这样最终我们就可以将链表排序好了。那么关键所在就是先分裂,在合并。代码如下所示:


   public ListNode sortList(ListNode head) {

       if (head == null || head.next == null)

           return head;


       // 使用两个指针,一快一慢,当快指针走到链表尾部时,慢指针正好到中间位置。

       ListNode prev = null, slow = head, fast = head;


       while (fast != null && fast.next != null) {

           prev = slow;

           slow = slow.next;

           fast = fast.next.next;

       }

       //prev表示第一个链表的尾部,所以指向空。slow为第二个指针的头部

       prev.next = null;


       // 继续分裂

       ListNode l1 = sortList(head);

       ListNode l2 = sortList(slow);


       // 当分裂到最后每个元素时,开始两两合并

       return merge(l1, l2);

   }


   //将两个有序链表合并的函数

   ListNode merge(ListNode l1, ListNode l2) {

       ListNode l = new ListNode(0), p = l;


       while (l1 != null && l2 != null) {

           if (l1.val < l2.val) {

               p.next = l1;

               l1 = l1.next;

           } else {

               p.next = l2;

               l2 = l2.next;

           }

           p = p.next;

       }


       if (l1 != null)

           p.next = l1;


       if (l2 != null)

           p.next = l2;


       return l.next;

   }


解析二 快速排序

另外一种方法就是快速排序法,快速排序的思路就是先将链表根据某个基础元素值分为两部分,比他大的和比他小的,然后一直这样分类下去,最后在进行合并即可,代码如下所示:


ListNode sortList(final ListNode h){

   if(h == null || h.next == null)

       return h;


   /*split into three list*/

   ListNode fakesmall = new ListNode(0), small = fakesmall;

   ListNode fakelarge = new ListNode(0), large = fakelarge;

   ListNode fakeequal = new ListNode(0), equal = fakeequal;


   ListNode cur = h; // pivot is h.

   while(cur != null){

       if(cur.val < h.val){

           small.next = cur;

           small = small.next;

       }

       else if(cur.val == h.val){

           equal.next = cur;

           equal = equal.next;

       }

       else{

           large.next = cur;

           large = large.next;

       }


       cur = cur.next;

   }


   // put an end.

   small.next = equal.next = large.next = null;

   // merge them and return . merge reusing below one. merge for quicksort should be simplified.

   return merge(merge(sortList(fakesmall.next), sortList(fakelarge.next)),fakeequal.next) ;

}


   ListNode merge(ListNode l1, ListNode l2) {

       ListNode l = new ListNode(0), p = l;


       while (l1 != null && l2 != null) {

           if (l1.val < l2.val) {

               p.next = l1;

               l1 = l1.next;

           } else {

               p.next = l2;

               l2 = l2.next;

           }

           p = p.next;

       }


       if (l1 != null)

           p.next = l1;


       if (l2 != null)

           p.next = l2;


       return l.next;

   }

更多资讯