LeetCode 148. Sort List（排序链表）

题目

求解

分析：题目要求时间复杂度是O（nlogn），我想到的是可以使用快排，但是数据是存在链表中的，我们只有第一个节点的引用，需要遍历链表，取出数据并排序，对原链表数据按照排序结果赋值，最后返回头结点。
过程：
1、保存头结点，取出数据保存在数组中。

    	ListNode firstNode=head;
    	if(head==null)
    		return null;
    	int[] a=new int[10000000];
    	int count=0;
        while(head!=null){
        	a[count++]=head.val;
        	head=head.next;
        }

2、快排。通过递归的排序，使得时间复杂度达到O（nlogn）。在这题中我发现Arrays.sort()方法不能使用，于是自己实现一个快排。

   public void quickSort(int[] a,int low,int high){
    	if(a.length<=0||low>=high){
    		return;
    	}
    	int left=low;
    	int right=high;
    	int num=a[left];
    	while(left<right){
    		while(a[right]>=num&&left<right){
    			right--;
    		}
    		a[left]=a[right];
    		while(a[left]<=num&&left<right){
    			left++;
    		}
    		a[right]=a[left];    		
    	}
    	a[left]=num;
    	quickSort(a, low, left-1);
    	quickSort(a, left+1, high);
    }

3、修改链表数据并返回头结点。

         count=0;
        head=firstNode;
        while(head!=null){
        	head.val=a[count++];
        	head=head.next;
        }
        return firstNode;