单链表的排序_

C

想去杭州的高级磨洋工在学习

int cmp(const void *a,const void *b)

{

return *(int*)a-*(int*)b;

}

struct ListNode* sortInList(struct ListNode* head ) {

int arr[100000]={0};

struct ListNode* head1=head;

struct ListNode* head2=head;

int i = 0;

int j = 0;

while(head1)

{

arr[i++]=head1->val;

head1=head1->next;

}

qsort(arr, i, sizeof(int), cmp);

while(head2)

{

head2->val=arr[j++];

head2=head2->next;

}

return head;

}

发表于 2024-04-13 23:09:31 回复(1)

C

南宫梦凝

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 the head node
 * @return ListNode类
 */
#include <stdlib.h>
int lenth(struct ListNode* p){
    int num = 0;
    while(p != NULL){
        num++;
        p = p->next;
    }
    return num;
}
void merge(int* waitsort, int left, int mid, int right){
    int i = left, j = mid + 1, k = 0;
    int* B = (int*)calloc(right - left + 1, sizeof(int));
    while(i <= mid && j <= right){
        if(waitsort[i] <= waitsort[j]){
            B[k++] = waitsort[i++];
        }else{
            B[k++] = waitsort[j++];
        }
    }
    while(i <= mid){
        B[k++] = waitsort[i++];
    }
    while(j <= right){
        B[k++] = waitsort[j++];
    }
    for(i = left, k = 0; i <= right; i++, k++){
        waitsort[i] = B[k];
    }
}
void mergeSort(int* waitsort, int left, int right){
    int mid;
    if(left < right){
        mid = (left + right) / 2;
        mergeSort(waitsort, left, mid);
        mergeSort(waitsort, mid + 1, right);
        merge(waitsort, left, mid, right);
    }
}
struct ListNode* sortInList(struct ListNode* head ) {
    // write code here
    struct ListNode* p = head;
    int len = lenth(p), i, j;
    int* waitSort = (int*)calloc(len,sizeof(int));
    //将链表中的数字放入数组
    for(i = 0; i < len; i++){
        waitSort[i] = p->val;
        p = p->next;
    }
    mergeSort(waitSort, 0, len - 1);
    p = head;
    for(i = 0; i < len; i++){
        p->val = waitSort[i];
        p = p->next;
    }
    return head;
}

编辑于 2024-04-08 15:42:05 回复(0)

C

牛客183552821号

多谢乐趣编程提供思路~

/**

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

*

* @param head ListNode类 the head node

* @return ListNode类

*/

#include <stdlib.h>

int cmp(const void *a,const void*b)

{

return *(int*)a>*(int*)b?1:-1;

}

struct ListNode* sortInList(struct ListNode* head ) {

// write code here

struct ListNode *a=head;

struct ListNode *b=head;

int k=0;

while(a!=NULL)

{

a=a->next;

k++;

}

int *buffer;

buffer=(int *)malloc(k*sizeof(int));

a=head;

int kk=0;

while (a!=NULL) {

buffer[kk++]=a->val;

a=a->next;

}

qsort(buffer, k, sizeof(int), cmp);

a=head;

kk=0;

while (a!=NULL) {

a->val=buffer[kk++];

a=a->next;

}

free(buffer);

return head;

}

编辑于 2024-03-24 10:19:05 回复(0)

C

一个优雅的程序猿

int cmp(const void*a,const void*b)
{
    return *(int*)a>*(int*)b?1:-1;
}
struct ListNode* sortInList(struct ListNode* head ) {
    struct ListNode *p;
    int *buffer,i=0;
    if(head==NULL || head->next==NULL)
        return head;
    i=0;
    p=head;
    while(p!=NULL) {
        i++;
        p = p->next;
    }
    buffer = (int*)malloc(i*sizeof(int));
    i=0;
    p=head;
    while(p!=NULL) {
        buffer[i++] = p->val;
        p = p->next;
    }
    qsort(buffer, i, sizeof(int), cmp);
    p=head;
    i=0;
    while(p!=NULL) {
        p->val = buffer[i++];
        p = p->next;
    }
    free(buffer);
    return head;
}

编辑于 2024-03-15 21:33:26 回复(1)

C

潮漫

快速排序不要用链表指针排，会超时，数组存储值，值排序后，直接覆盖链表节点的值

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

int *res;

void quicksort(int * res,int l,int r){

if(l>=r)return;

int base=res[l];

int ll=l,rr=r;

while (l<=r) {

if(l==r){

res[l]=base;

break;

}

while (l<r&&res[r]>=base) r--;

if (l<r) {

res[l++]=res[r];

}

while (l<r&&res[l]<=base)l++;

if(l<r)res[r--]=res[l];

}

quicksort(res, ll, l-1);

quicksort(res, l+1, rr);

}

struct ListNode* sortInList(struct ListNode* head ) {

// write code here

//time_t s,e;

//s=time(NULL);

res=malloc(sizeof(int)*100001);

int n=0;

struct ListNode*t=head;

while (t!=NULL) {

res[n++]=t->val;

t=t->next;

}

//e=time(NULL);

//printf("%f",difftime(e,s));

quicksort(res,0,n-1);

t=head;

n=0;

while (t!=NULL) {

t->val=res[n++];

t=t->next;

}

return head;

}

发表于 2024-01-21 12:29:27 回复(0)

C

牛客123555699号

快速排序，大数据量下，速度更快，小数据量下，提升不大

struct ListNode* sortInList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }

    // Split the list into two halves
    struct ListNode* slow = head;
    struct ListNode* fast = head->next;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    struct ListNode* secondHalf = slow->next;
    slow->next = NULL;

    // Sort each half recursively
    struct ListNode* left = sortInList(head);
    struct ListNode* right = sortInList(secondHalf);

    // Merge the sorted halves
    struct ListNode dummy;
    struct ListNode* tail = &dummy;
    while (left != NULL && right != NULL) {
        if (left->val < right->val) {
            tail->next = left;
            left = left->next;
        } else {
            tail->next = right;
            right = right->next;
        }
        tail = tail->next;
    }
    if (left != NULL) {
        tail->next = left;
    } else if (right != NULL) {
        tail->next = right;
    }

    return dummy.next;
}

发表于 2023-10-05 17:42:17 回复(0)

C

牛客820577006号

/**

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

/**

*

* @param head ListNode类 the head node

* @return ListNode类

*/

struct ListNode* sortInList(struct ListNode* head ) {

// write code here

struct ListNode * p = head->next;

head->next=NULL;

struct ListNode *last = head;

struct ListNode *pk=head;

struct ListNode *pr=pk;

struct ListNode*pf=p;

while(p)

{

if(p->val < pk->val && pk == head)

{

pf=p;

p=p->next;

pf->next = head;

head=pf;

pk=head;

continue;

}

else if(p->val > pk ->val && pk->next == NULL)

{

pf=p;

p=p->next;

pf->next=NULL;

last->next = pf;

last=pf;

pk=head;

continue;

}

else if(p->val < pk->val){

pf=p;

p=p->next;

pf->next =NULL;

pr->next=pf;

pf->next = pk;

pk=head;

continue;

}

else if(p->val > pk->val)

{

pr=pk;

pk=pk->next;

continue;

}

return head;

}

发表于 2023-04-06 11:15:19 回复(0)

C

帅奶哟。

#include <stdlib.h>

int privot(int a[], int low, int high);
void quicksort(int a[], int low, int high);

struct ListNode* sortInList(struct ListNode* head ) {
    // write code here
    int s[100000] = {0};
    int i = 0;
    struct ListNode *p = head;

    //将每个节点的val存入数组s中
    while (p) {
        s[i++] = p->val;
        p = p->next;
    }
    
    //快排
    quicksort(s, 0, i-1);
    p = head;
    i = 0;

    //重新给链表赋值val
    while (p) {
        p->val = s[i++];
        p = p->next;
    }

    return head;
}
//划分
int privot(int a[], int low, int high){
    int temp = a[low];
    while (low < high) {
        while (low < high && a[high] >= temp) high--;
        a[low] = a[high];
        while (low < high && a[low] <= temp) low++;
        a[high] = a[low];
    }
    a[low] = temp;
    return low;
}
//快排
void quicksort(int a[], int low, int high){
    if (low < high) {
        int pri = privot(a, low, high);
        quicksort(a, low, pri-1);
        quicksort(a, pri+1, high);
    }
}

发表于 2023-03-20 13:57:28 回复(0)

C

爱唱歌的黑眼圈

放到数组里快排，再放回去

int cmp(void const*a,void const*b){
    return *(int*)a-*(int*)b;
}
struct ListNode* sortInList(struct ListNode* head ) {
    // write code here
    int size=0;
    struct ListNode* p=head;
    while(p!=NULL){
        size++;
        p=p->next;
    }
    
    p=head;
    int i=0;
    int*arr=malloc(sizeof(int)*size);
    while(p!=NULL){
        arr[i]=p->val;
        i++;
        p=p->next;
    }
    
    qsort(arr,size,sizeof(int),cmp);
    p=head;
    i=0;
    while(p!=NULL){
        p->val =arr[i];
        i++;
        p=p->next;
    }
    return head;
}

发表于 2023-02-22 20:29:39 回复(0)

C

牛客354365918号

/**

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

/**

*

* @param head ListNode类 the head node

* @return ListNode类

*/

struct ListNode* sortInList(struct ListNode* head )

{

if(head == NULL)

{

return NULL;

}

//定义两个指针遍历

struct ListNode *p = NULL;

struct ListNode *q = NULL;

struct ListNode *h = head;

int temp;

//遍历链表比较大小（冒泡）

while(h->next!=NULL)

{

p = head;

q = head;

while(q->next!=NULL)

{

if(p->val > p->next->val)

{

temp = p->next->val;

p->next->val = q->val;

q->val = temp;

}

q = q->next;

p = p->next;

}

h = h->next;

}

return head;

}

发表于 2022-11-09 16:15:40 回复(0)

C

tao_w

void shell_sor(int* a,int n)

{

int gap=n;

while(gap)

{

gap/=2;

for(int i=0;i<n-gap;i++)

{

int end=i;

int tmp=a[end+gap];

while(end>=0)

{

if(a[end]>tmp)

{

a[end+gap]=a[end];

end-=gap;

}

else

{

break;

}

a[end+gap]=tmp;

}

struct ListNode* sortInList(struct ListNode* head ) {

int count=0;

struct ListNode* cur=head;

while(cur) //计算链表中元素的大小，以便于后续动态开辟内存空间

{

count++;

cur=cur->next;

}

int* arr=(int* )malloc(count*sizeof(int));

cur=head;

int i=0;

while(cur) //将链表的具体数值复制到数组中

{

arr[i++]=cur->val;

cur=cur->next;

}

//利用时间复杂度为O(nlogn)的希尔排序方法对数组进行排序

shell_sor(arr,count);

struct ListNode* rethead=NULL,*rettail=NULL;

for(int i=0;i<count;i++)

{

struct ListNode* newnode=(struct ListNode*)malloc(sizeof(struct ListNode));

newnode->val=arr[i];

newnode->next=NULL;

if(rethead==NULL)

{

rethead=rettail=newnode;

}

else

{

rettail->next=newnode;

rettail=newnode;

}

return rethead;

}

发表于 2022-10-29 12:52:52 回复(0)

C

苦闷的伊登offer多多

王道代码：

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */

/**
 *
 * @param head ListNode类 the head node
 * @return ListNode类
 */
struct ListNode* sortInList(struct ListNode* head ) {
    // write code here
    if (head == NULL) return NULL;
    struct ListNode *H=malloc(sizeof(struct ListNode));
    H->next=head;
    struct ListNode* pre,*p=head,*r=p->next;
    p->next = NULL;
    p=r;
    while (p) {
        pre = H;
        r = p->next;
        while(pre->next!=NULL&&pre->next->val < p->val) {
            pre = pre->next;
        }
        p->next = pre->next;
        pre->next = p;
        p =r;
    }
    return H->next;
}

发表于 2022-10-26 22:44:47 回复(3)

C

0wning

使用递归解题！

/**

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

/**

*

* @param head ListNode类 the head node

* @return ListNode类

*/

struct ListNode* sortInList(struct ListNode* head ) {

// write code here

// 初步考虑使用递归解题！

// 每次返回一个已经排序好的链表，递归下去。

// 考虑到每次返回的链表必为一个排序好的链表，使用插入法将新的值插入到链表中

// 然后返回链表

struct ListNode* l1 = head;

struct ListNode* tmpx = NULL;

struct ListNode* tmp = NULL;

struct ListNode* tmpH = NULL;

if(l1==NULL) { // 空节点

return NULL;

}

if(l1&&l1->next == NULL) { //只有一个节点

return l1;

}

if(l1&&l1->next&&l1->next->next==NULL) { //有两个节点

if(l1->val<=l1->next->val){

return l1;

}else{ // 交换两个节点的顺序

tmp = l1->next;

tmp->next = l1;

l1->next = NULL;

return tmp;

}

// 调整 l1 节点和 l1 节点后序节点链表l1的顺序关系。

l1->next = sortInList(l1->next); // 运行到这里，此时 l1->next 必存在

tmpH = tmp = l1->next;

tmpx = l1;

if(tmpx->val <= tmp->val) { //开始时

return l1;

}

while(tmp) {

if(tmp->next) {

if(tmpx->val>=tmp->val && tmpx->val<=tmp->next->val){ // 选择合适的地方进行插入

tmpx->next = tmp->next;

tmp->next = tmpx;

return tmpH;

}else if (tmp->next->next==NULL) { // 结束时

tmp->next->next = tmpx;

tmpx->next = NULL;

return tmpH;

}

tmp = tmp->next;

}

return tmpH;

}

发表于 2022-10-23 10:39:19 回复(0)

C

Hayaizo

void bubble_sort(int arr[],int sz){
    int i=0,j=0;
    for(i=0;i<sz-1;i++){
        for(j=0;j<sz-i-1;j++){
            if(arr[j]>arr[j+1]){
                int tmp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=tmp;
            }
        }
    }
}

struct ListNode* sortInList(struct ListNode* head ) {
    struct ListNode*tail=head;
    int cnt=0;
    while(tail){
        tail=tail->next;
        cnt++;
    }
    int *nums=(int *)malloc(sizeof(int)*cnt);
    tail=head;
    int index=0;
    while(tail){
        nums[index++]=tail->val;
        tail=tail->next;
    }
    //冒泡排序
    bubble_sort(nums,cnt);
    tail=head;
    int i=0;
    //数组转链表
    while(tail){
        tail->val=nums[i++];
        tail=tail->next;
    }
    return head;
}

发表于 2022-09-10 14:27:35 回复(0)

C

阿金要努力

int cmp(const void* a,const void* b)
{
    return *(int*)a-*(int*)b;
}
struct ListNode* sortInList(struct ListNode* head ) 
{
    // write code here
    int count=0;
    struct ListNode* tail=head;
    while(tail)
    {
        tail=tail->next;
        count++;
    }
    int* arr=(int*)malloc(sizeof(int)*count);
    int i=0;
    tail=head;
    while(tail)
    {
        arr[i]=tail->val;
        tail=tail->next;
        i++;
    }
    qsort(arr, count, sizeof(int), cmp);
    tail=head;
    for(int i=0;i<count;i++)
    {
        tail->val=arr[i];
        tail=tail->next;
    }
    return head;
}

发表于 2022-05-04 01:15:30 回复(0)

C

莫小雨so

/**
 * 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;
}

发表于 2022-03-04 12:07:49 回复(0)

C

出来看看

链表转数组 + 快排

void quickSorted(int *nums, int left, int right){
    if (left > right) return;
    int i = left, j = right, temp = nums[left];
    while (i < j){
        while (i < j && temp <= nums[j])
            j--;
        if (i < j)
            nums[i++] = nums[j];
        while (i < j && temp > nums[i])
            i++;
        nums[j--] = nums[i];
    }
    nums[i] = temp;
    quickSorted(nums, left, i - 1);
    quickSorted(nums, i + 1, right);
}

struct ListNode* sortInList(struct ListNode* head ) {
    int length = 0;
    struct ListNode *cur = head;
    while(cur){
        length++;
        cur = cur->next;
    }
    int *nums = (int*)malloc(sizeof(int) * length);
    cur = head;
    int index = 0;
    //链表转数组
    while (cur){
        nums[index++] = cur->val;
        cur = cur->next;
    }
    quickSorted(nums, 0, length - 1);
    cur = head;
    int i = 0;
    //数组重新转链表
    while (cur){
        cur->val = nums[i++];
        cur = cur->next;
    }
    return head;
}

发表于 2021-11-12 11:16:19 回复(0)

单链表的排序

输入

输出

输入

输出

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题