精华内容
下载资源
问答
  • 链表排序

    万次阅读 2017-06-08 23:06:56
    在 O(n log n) 时间复杂度和常数级的空间复杂度下给链表排序。 您在真实的面试中是否遇到过这个题?  Yes 样例 给出 1->3->2->null,给它排序变成 1->2->3->null. import java.util....

    在 O(n log n) 时间复杂度和常数级的空间复杂度下给链表排序。

    样例

    给出 1->3->2->null,给它排序变成 1->2->3->null.

    import java.util.Scanner;
    
    /**
     * 在 O(n log n) 时间复杂度和常数级的空间复杂度下给链表排序。
    样例
    给出 1->3->2->null,给它排序变成 1->2->3->null.
     *对链表分别进行快速排序和归并排序
     * @author Dell
     *
     */
    public class Test98 {
       public static ListNode sortList(ListNode head)
       {
    	   quicksort(head,null);
    	return head;
     
       }
       //链表的快速排序
       public static ListNode partition(ListNode start,ListNode end)
       {
    	    int x=start.val;
    	    ListNode i=start;
    	    ListNode j=i.next;
    	   while(j!=end)
    	   {
    		   if(j.val<x)
    		   {
    			   i=i.next;
    			   int temp=i.val;
    			   i.val=j.val;
    			   j.val=temp;  
    		   }
    		   j=j.next;
    	   }
    	   
    	   int temp1=i.val;
    	   i.val=start.val;
    	   start.val=temp1;
    	   return i;  
       }
       public static void quicksort(ListNode begin,ListNode end)
       {
    	   if(begin!=end)
    	   {
    		   ListNode p=partition(begin,end);
    		   quicksort(begin,p);
    		   quicksort(p.next,end);	   
    	   }
    	   
       }
       
       //链表的归并排序
       public static ListNode Merge(ListNode A, ListNode B)
       {
    	   ListNode p=A;
    	   ListNode q=B;
    	   ListNode result=new ListNode(-1);
    	   ListNode r=result;
    	   while(p!=null&&q!=null)
    	   {
    		   if(p.val<q.val)
    		   {
    			   r.next=p;
    			   p=p.next;
    		   }
    		   else
    		   {
    			   r.next=q;
    			   q=q.next;   
    		   }
    		   r=r.next;
    	   }
    	 if(p!=null)
    	 {
    		 r.next=p;
    	 }
    	 if(q!=null)
    	 {
    		 r.next=q;
    	 }
    	 return result.next;  
       }
       
       public static ListNode Mergesort(ListNode head)
       {
    	   if(head==null||head.next==null)
    		   return head;
    	   
    		   ListNode mid=find(head);
    		   ListNode later=mid.next;
    		   mid.next=null;
    		return Merge(Mergesort(head),Mergesort(later));
    	 
         
       }
       public static ListNode find(ListNode head)
       {
    	   ListNode slow=head;
    	   ListNode fast=head;
    	   while(fast.next!=null&&fast.next.next!=null)
    	   {
    		   slow=slow.next;
    		   fast=fast.next.next;
    	   }
    	   return slow;
       }
       public static ListNode sortList1(ListNode head)
       {
    	   
    	return Mergesort(head);
     
       }
    	public static void main(String[] args) {
          Scanner sc=new Scanner(System.in);
          int n=sc.nextInt();
          ListNode list=new ListNode(-1);
          ListNode p=list;
          for(int i=0;i<n;i++)
          {
        	  ListNode temp=new ListNode(sc.nextInt());
        	  p.next=temp;
        	  p=p.next;
          }
          ListNode result=sortList1(list.next);
          while(result!=null)
          {
        	  System.out.print(result.val+" ");
        	  result=result.next;
          }
    	}
    
    }
    



    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 28,351
精华内容 11,340
关键字:

链表排序