你的位置:首页 > Java教程

[Java教程]148. Sort List


Sort a linked list in O(n log n) time using constant space complexity.

代码如下:

 1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *   int val; 5  *   ListNode next; 6  *   ListNode(int x) { val = x; } 7  * } 8 */ 9 public class Solution {10   public ListNode sortList(ListNode head) {11     if(head==null||head.next==null)12     return head;13     14     ListNode p=head;15     int count=0;16     17     while(p!=null)18     {19       count++;20       p=p.next;21     }22     int[]a=new int[count];23     int c=count;24     p=head;25    for(int i=0;i<count;i++)26     {27      if(p!=null)28      a[i]=p.val;29      p=p.next;30     }31    p=head;32    33     Arrays.sort(a);34     for(int i=0;i<c;i++)35     {36       p.val=a[i];37       p=p.next;38     }39     return head;40   }41 }