找单链表中第n小的数

请问怎么用单链表找到第n个最小值呢 并删除，比如，4，3，2，1，第二小的是2，找到2并删除它

链表是有序链表的话，直接找到第2个节点，让第1个节点指向第3个节点，然后释放第2个节点的内存即可。
如果是无序链表，就需要遍历，依次找出最小值、次小值。。。直到找到需要的节点，然后让改节点的上一个节点指向该节点的下一个节点。
下面的代码是删除无序链表节点。

代码：

#include <stdio.h>
#include <stdlib.h>

struct StNode 
{
    int data;
    struct StNode* next;
};

struct StNode* CreateList()
{
    struct StNode* head;
    struct StNode* p;
    struct StNode* t;
    int n,v,i;
    head = (struct StNode*)malloc(sizeof(struct StNode));
    head->next = NULL;
    p = head;
    printf("请输入链表元素的个数：");
    scanf("%d",&n);
    printf("请输入链表数据：");
    for(i=0;i<n;i++)
    {
        t = (struct StNode*)malloc(sizeof(struct StNode));
        scanf("%d",&v);
        t->data = v;
        t->next = NULL;
        p->next = t;
        p = t;
    }
    return head;
}

int GetLength(struct StNode* head)
{
    int len= 0;
    struct StNode* p ;
    if(head == 0) return 0;
    p = head->next;
    while(p)
    {
        len++;
        p=p->next;
    }
    return len;
}


//判断节点是否已经在数组中
int isInarry(struct StNode* pmin,struct StNode* arry[],int n)
{
    int i;
    for (i=0;i<n;i++)
    {
        if(pmin == arry[i])
            return 1;
    }
    return 0;
}


//查找第n小的数，并删除,n要小于链表的长度
struct StNode* DeleteNode(struct StNode* head,int n)
{
    struct StNode* p;
    struct StNode* pmin,*pre;
    struct StNode* arr[100];
    int i=0,j=0,nmb=0;

    while(nmb < n)
    {
        pmin = head->next;
        while (pmin)
        {
            //查看pmin是否已经在数组中
            if(!isInarry(pmin,arr,nmb))
                break;
            else
                pmin = pmin->next;
        }
        //查找最小的数
        p = head->next;
        while (p)
        {
            if( (p->data < pmin->data) && (!isInarry(p,arr,nmb)) )
                pmin = p;
            p = p->next;
        }
        arr[nmb] = pmin;
        nmb++;
    }
    //删除
    pre = head;
    p=head->next;
    while(p)
    {
        if(p==arr[nmb-1])
            break;
        else
        {
            pre = p;
            p=p->next;
        }
    }
    if(p)
    {
        pre->next = p->next;
        free(p);
        p = 0;
    }
    return head;
}

//显示列表
void show(struct StNode* head)
{
    struct StNode* p=head->next;
    while(p)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}
void Release(struct StNode* head)
{
    struct StNode* p;
    while(head)
    {
        p = head->next;
        free(head);
        head = p;
    }
    head = 0;
}

int main()
{
    int n,len;
    struct StNode* head = CreateList();
    printf("链表数据为：");
    show(head);
    len = GetLength(head);
    while(1)
    {
        printf("请输入需要删除的第n小的值：");
        scanf("%d",&n);
        if(n>0 && n<=len)
            break;
    }
    head = DeleteNode(head,n);
    printf("删除节点后，链表数据为：");
    show(head);
    Release(head);
    return 0;
}

您好，我是有问必答小助手，您的问题已经有小伙伴帮您解答，感谢您对有问必答的支持与关注！
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632