单链表按一个基准值划分

Question

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct LinkNode
{
    int data;
    struct LinkNode *next;
}LinkNode;
void InitList(LinkNode *&L)
{
    L=(LinkNode*)malloc(sizeof(LinkNode));
    L->next=NULL;
}
void CreatList(LinkNode *&L,int a[],int n)
{
    LinkNode *s;
    L=(LinkNode*)malloc(sizeof(LinkNode));
    L->next=NULL;
    for(int i=0;i<n;i++)
    {
        s=(LinkNode*)malloc(sizeof(LinkNode));
        s->data=a[i];
        s->next=L->next;
        L->next=s;
    }
}
void DisList(LinkNode *L)
{
    LinkNode *p=L->next;
    while(p!=NULL)
    {
        printf("\t%d",p->data);
        p=p->next;
    }
    printf("\n");
}
bool sad(int e,LinkNode *L)
{
    LinkNode *p=L->next;
    while(p!=NULL)
    {
        if(p->data==e)
        {
            break;
        }
        p=p->next;
    }
    if(p==NULL)
    {
        return false;
    }
    else
    {
        return true;
    }
}
void fun(int a[],int n)
{
    int j=0,i=1;
    int t;
    for(i=1;i<=n-1;i++)
    {
        for(j=0;j<=n-1-i;j++)
    {
        if(a[j]>a[j+1])
        {
            t=a[j];
            a[j]=a[j+1];
            a[j+1]=t;
        }
    }
    }
    for(int k=0;k<n;k++)
    {
        printf("\t%d",a[k]);
    }
}
void sort(LinkNode *&L)
{
    LinkNode *p,*pre,*q;
    p=L->next->next;
    L->next->next=NULL;
    while(p!=NULL)
    {
        q=p->next;
        pre=L;
        while(pre->next!=NULL&&pre->next->data<p->data)
        {
            pre=pre->next;
        }
        p->next=pre->next;
        pre->next=p;
        p=q;
    }
}
int main()
{
    int n,e[100];
    int x;
    LinkNode *L;
    scanf("%d",&n);
    for(int i=0;i<n;++i)
    {
        scanf("%d",&e[i]);
    }
    scanf("%d",&x);
    InitList(L);
    CreatList(L,e,n);
    DisList(L);
    sort(L);
    DisList(L);

}
//该题需要相对位置保持不变，但是我实在不知道要写什么样的函数才能使其相对位置不变......
我的输入：7 10 8 30 56 28 7 46
30
我的输出：46 7 28 56 30 8 10
7 8 10 28 30 46 56
题目需要的输出：（与上面一致）
7 28 8 10 30 46 56

麻烦各路神仙帮助我，怎么样才能使相对位置不变啊？

Answer 1

修改如下，供参考：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct LinkNode
{
    int data;
    struct LinkNode *next;
}LinkNode;
void InitList(LinkNode *&L)
{
    L=(LinkNode*)malloc(sizeof(LinkNode));
    L->next=NULL;
}
void CreatList(LinkNode* L,int a[],int n)
{
    LinkNode *s;
    for(int i=0;i<n;i++)
    {
        s=(LinkNode*)malloc(sizeof(LinkNode));
        s->data=a[i];
        s->next=L->next;
        L->next=s;
    }
}
void DisList(LinkNode *L)
{
    LinkNode *p=L->next;
    while(p!=NULL)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
}

void sort(LinkNode* L,int num)
{
    LinkNode *p= L->next,*t = NULL, *h = NULL, *s = NULL; //以下修改
    L->next = NULL;
    while (p) {
        t = p;
        p = p->next;
        t->next = NULL;
        if (!L->next)
            L->next = t;
        else if (t->data > num)
        {
            h = L;
            while (h->next) h = h->next;
            h->next = t;
        }
        else {
            h = L->next; s = L;
            while (h && h->data < num) s = h, h = h->next;
            if (s == L) {
                t->next = L->next;
                L->next = t;
            }
            else {
                t->next = s->next;
                s->next = t;
            }
        }
    }
}
int main()
{
    int n,e[100];
    int x;
    LinkNode *L;
    InitList(L);

    scanf("%d",&n);
    for(int i=0;i<n;++i)
        scanf("%d",&e[i]);
    scanf("%d",&x);

    CreatList(L,e,n);
    DisList(L);

    sort(L , x);
    DisList(L);
   
    return 0;
}

//以下函数多余 删除
bool sad(int e,LinkNode *L)
{
    LinkNode *p=L->next;
    while(p!=NULL)
    {
        if(p->data==e)
        {
            break;
        }
        p=p->next;
    }
    if(p==NULL)
    {
        return false;
    }
    else
    {
        return true;
    }
}
void fun(int a[],int n)
{
    int j=0,i=1;
    int t;
    for(i=1;i<=n-1;i++)
    {
        for(j=0;j<=n-1-i;j++)
    {
        if(a[j]>a[j+1])
        {
            t=a[j];
            a[j]=a[j+1];
            a[j+1]=t;
        }
    }
    }
    for(int k=0;k<n;k++)
    {
        printf("\t%d",a[k]);
    }
}

运行图：