题解 | #单链表的排序#
单链表的排序
http://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
/**
*
* @param head ListNode类 the head node
* @return ListNode类
*/
#设置一个辅助数组拷贝出链表中的值，用归并排序来进行排序后又拷贝回链表中
#include<stdlib.h>
void merge(int *arr,int lo, int mid, int hi);
void mergeSort(int *arr,int lo, int hi)
{
if(lo == hi) return;
int mid = (lo +hi) >> 1;
mergeSort(arr, lo, mid);
mergeSort(arr, mid + 1, hi);
merge(arr, lo ,mid, hi);
}
void merge(int *arr,int lo, int mid, int hi)
{
int *B = (int*)malloc((mid -lo + 1)*sizeof(int));
int i = 0, j = 0, k = 0;
for(j = lo; j <= mid; j++)
{
*(B + (i ++)) = *(arr + j);
}
for(i = 0, k = lo, j = mid +1; i <= mid -lo;)
{
*(arr + (k++)) = *(B + i) < *(arr + j) || j > hi ? *(B + (i ++)) : *(arr + (j++));
}
free(B);
}
struct ListNode* sortInList(struct ListNode* head ) {
// write code here
int *arr = (int*)malloc(100000*sizeof(int));
int i = 0, len = 0;
struct ListNode *p = head;
while(p)
{
*(arr + (i ++)) = p->val;
p = p->next;
}
len = i;
mergeSort(arr, 0, len - 1);
p = head;
i = 0;
while(p)
{
p->val = *(arr + (i ++));
p = p->next;
}
free(arr);
return head;
}
