首页 > 试题广场 >

单链表的排序

[编程题]单链表的排序
  • 热度指数：160060 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个节点数为n的无序单链表，对其按升序排序。

数据范围：，保证节点权值在[-10^9,10^9]之内。
要求：空间复杂度 ，时间复杂度

示例1

输入

[1,3,2,4,5]

输出

{1,2,3,4,5}
示例2

输入

[-1,0,-2]

输出

{-2,-1,0}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
C
湫湫宁头像 湫湫宁 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 the head node
 * @return ListNode类
 */
#include <stdlib.h>

#include <stdio.h>  

// 快速排序的分区函数  
int partition(int arr[], int low, int high) {  
    int pivot = arr[high]; // 选择最后一个元素作为基准  
    int i = (low - 1); // 小于基准的元素的索引  

    for (int j = low; j < high; j++) {  
        if (arr[j] < pivot) { // 如果当前元素小于基准  
            i++; // 增加小于基准的元素索引  
            // 交换 arr[i] 和 arr[j]  
            int temp = arr[i];  
            arr[i] = arr[j];  
            arr[j] = temp;  
        }  
    }  
    // 将基准元素放到正确的位置  
    int temp = arr[i + 1];  
    arr[i + 1] = arr[high];  
    arr[high] = temp;  
    
    return i + 1; // 返回基准元素的索引  
}  

// 快速排序的递归函数  
void quickSort(int arr[], int low, int high) {  
    if (low < high) {  
        // 找到分区点  
        int pi = partition(arr, low, high);  
        
        // 递归排序分区点两侧的元素  
        quickSort(arr, low, pi - 1);  
        quickSort(arr, pi + 1, high);  
    }  
}  
struct ListNode* sortInList(struct ListNode* head ) {
    // write code here
    struct ListNode* phead = (struct ListNode*)malloc(sizeof(struct ListNode));
    phead->next = head;
    struct ListNode* p = phead->next;
    struct ListNode*p1 = p;
    int minval = head->val, i = 0;
    int a[100000] = {};

    while(p)
    {
        a[i] = p->val;
        p = p->next;
        i++;
    }
    quickSort(a,0 ,i-1);
    i = 0;
    while(p1)
    {
        p1->val = a[i];
        p1 = p1->next;
        i++;
    }
    return phead->next;
}
取巧的方法，先转换成数组，将其排序后，再放到链表里面，但是此处若是使用冒泡***出现超时。只能通过快速排序法，使时间尽量少。
发表于 2024-08-15 11:29:32 回复(0)
C
小小卿灵头像 小小卿灵
struct ListNode* merge(struct ListNode* l1, struct ListNode* l2) {
struct ListNode dummy;
struct ListNode* tail = &dummy;
dummy.next = NULL;

while (l1 && l2) {
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}

tail->next = l1 ? l1 : l2;
return dummy.next;
}

struct ListNode* split(struct ListNode* head) {
if (!head || !head->next) return head;

struct ListNode dummy;
struct ListNode* slow = &dummy, *fast = head;
dummy.next = head;

while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}

struct ListNode* second = slow->next;
slow->next = NULL;
return second;
}

struct ListNode* sortInList(struct ListNode* head) {
if (!head || !head->next) return head;

struct ListNode* second = split(head);
head = sortInList(head);
second = sortInList(second);

return merge(head, second);
}
发表于 2024-05-14 09:42:38 回复(0)
C
StellarVibes头像 StellarVibes
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号头像 牛客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号头像 牛客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号头像 牛客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号头像 牛客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
已注销头像 已注销
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多多头像 苦闷的伊登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头像 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头像 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 回复(1)
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)
提交观点

问题信息

链表 排序
难度：
26条回答 11788浏览

热门推荐

通过挑战的用户

查看代码

相关试题

单链表的排序

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号