首页 > 试题广场 >

单链表排序

[编程题]单链表排序
  • 热度指数：974 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
请实现list_sort，使用冒泡法将head指向的链表按val值大小排成升序
struct node {
    int val;
    struct node *next;
};
void list_sort(struct node *head)
{
}


输入描述:
第一行为数据个数 第二行为输入的数据，以空格进行分隔


输出描述:
输出head指向的链表数据，以空格分隔
示例1

输入

12
10 22 2 5 9 8 1 33 4 6 7 9

输出

1 2 4 5 6 7 8 9 9 10 22 33
算法知识视频讲解
添加回答
黑莓婆婆头像 黑莓婆婆 
static void list_sort(struct node *head)
{
    //TODO:
    if (!head) return;
    struct node *r = NULL;
    struct node *p, *q;
    while (head->next != r) {
        p = head;
        while (p->next != r) {
            q = p->next;
            if (p->val > q->val) {
                int t = p->val;
                p->val = q->val;
                q->val = t;
            }
            p = q;
        }
        r = p;
    }
}

发表于 2021-07-11 19:19:15 回复(0)
Italink头像 Italink 
#include <stdio.h>
#include <malloc.h>
#include <algorithm>
 
struct node {
    int val;
    struct node* next;
};
 
static void list_sort(struct node* head);
 
struct node* list_create(int arr[], int size)
{
    struct node* head = NULL;
    int i;
    for (i = size - 1; i >= 0; --i) {
        struct node* p = (struct node*)malloc(sizeof(struct node));
 
        p->val = arr[i];
        p->next = head;
        head = p;
    }
    return head;
}
static void list_print(struct node* head)
{
    for (; head; head = head->next) {
        printf("%d", head->val);
        if (head->next)
            printf(" ");
    }
    printf("\n");
}
static void list_free(struct node* head)
{
    struct node* next;
    while (head) {
        next = head->next;
        free(head);
        head = next;
    }
}
static int input(int** arr, int* size)
{
    int i;
    int ret;
 
    ret = fscanf(stdin, "%d\n", size);
    if (ret != 1)
        return -1;
    *arr = (int*)malloc(sizeof(int) * (*size));
    for (i = 0; i < *size; ++i) {
        fscanf(stdin, "%d ", &(*arr)[i]);
    }
    return 0;
}
 
int main(int argc, char* argv[])
{
    struct node* head;
    int* arr = NULL;
    int size = 0;
 
    if (input(&arr, &size) < 0) {
        fprintf(stderr, "input error\n");
        return 0;
    }
    head = list_create(arr, size);
    list_sort(head);
    list_print(head);
    list_free(head);
    free(arr);
    return 0;
}
 
static void list_sort(struct node* head)
{
    for (node* i = head; i; i=i->next) {
        for (node* j = i->next; j; j = j->next) {
            if (i->val > j->val)
                std::swap(i->val, j->val);
        }
    }
}

发表于 2020-06-05 19:03:10 回复(0)
C/C++
小牛向前冲_头像 小牛向前冲_ 
static void list_sort(struct node *head)
{
    //TODO:
    struct node* cur = head;
    struct node* loop = head;
    while (loop)
    {
        cur = head;
        while (cur->next)
        {
            struct node* next = cur->next;
            if (cur->val > next->val) std::swap(cur->val, next->val);
            cur = cur->next;
        }
        loop = loop->next;
    }
}

发表于 2023-09-05 21:20:23 回复(0)
牛客469834578号头像 牛客469834578号 
static void list_sort(struct node *head)
{
    //TODO:
    struct node *temp=head;
    for(struct node *q=head;q!=NULL;q=q->next)
        for(struct node *p =q->next;p!=NULL;p=p->next)
        {
            int temp =q->val;
            if(q->val>p->val)
            {
                q->val = p->val;
                p->val=temp;
            }
        }
}

发表于 2020-08-24 17:50:16 回复(0)
提交观点

问题信息

C++工程师 深信服
来自：深信服校园招聘c/c ...
上传者：小小
难度：
4条回答 3371浏览

热门推荐

通过挑战的用户

相关试题

单链表排序

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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