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

typedef struct Node
{
    int data; //数据域
    struct Node * pNext; //指针域
}NODE, * PNODE;

PNODE create_linklist(); //创建不带头结点的单链表
bool delete_nodes(PNODE *, int, int); //删除从指定位置开始的连续多个节点
int length_linklist(PNODE); //求链表长度
void traverse_linklist(PNODE); //遍历输出链表

int main(void)
{
    int pos;
    int num;
    PNODE list = NULL;
    list = create_linklist();

    printf("删除前的链表：\n");
    traverse_linklist(list);

    printf("请输入你要删除的位置：\n");
    scanf("%d", &pos);

    printf("请输入你要连续删除的节点个数：\n");
    scanf("%d", &num);

    if(delete_nodes(&list, pos, num))
    {
        printf("删除成功！\n");
    }
    else
    {
        printf("删除失败！\n");
    }
    
    printf("删除后的链表：\n");
    traverse_linklist(list);


    return 0;
}

PNODE create_linklist()
{
    int len; //用来存储链表长度
    int val; //用来暂时存储某个节点的数据域
    int i; //循环变量

    PNODE list = (PNODE)malloc(sizeof(NODE));
    if(!list)
    {
        printf("分配失败，程序退出！\n");
        exit(-1);
    }

    printf("请输入你要生成的链表长度：\n");
    scanf("%d", &len);

    //如果长度为零
    if(0 == len)
    {
        list = NULL;
        return list;
    }

    //不为0
    printf("请输入链表第1个节点的值：\n");
    scanf("%d", &val);

    //为第一个节点的数据域赋值
    list->data = val;
    list->pNext = NULL;

    //长度为1
    if(1 == len)
        return list;

    //创建一个始终指向链表尾节点的指针，初始指向第一个节点
    PNODE pTail = list;
    pTail->pNext = NULL;

    //长度不为1，为第二个及后续节点的数据域赋值
    for (i = 1; i < len; i++)
    {
        printf("请输入链表第%d个节点的值：\n", i+1);
        scanf("%d", &val);

        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        if(!pNew)
        {
            printf("分配失败，程序退出！\n");
            exit(-1);
        }

        //为新生成节点的数据域赋值
        pNew->data = val;

        //原链表的尾节点挂在新生成节点上
        pTail->pNext = pNew;

        //新生成节点变为新的尾节点，将其指针域指向空
        pNew->pNext = NULL;

        //pTail后移，使其始终指向链表的尾节点
        pTail = pNew;
    }

    printf("链表创建成功！\n");

    return list;
}

//传入参数中有指向链表第一个节点的指针的指针，是为了方便进行删除第一个节点的操作
//删除第一个节点，需要将新的指向第一个节点的指针，返回给主函数，利用二级指针操作
bool delete_nodes(PNODE * list, int pos, int num)
{
    int i; //循环变量
    PNODE p = * list; 
    PNODE q; //用来暂时保存p的值，方便释放节点空间
    PNODE r; //指向pos所在节点的前驱节点

    //如果发删除位置不对，删除失败，返回false
    if(pos < 1 || pos > length_linklist(*list))
        return false;
    
    //如果链表长度为0，删除失败，返回false
    if(!length_linklist(*list))
        return false;

    //如果开始删除的位置是第一个节点
    if(pos == 1)
    {
        //删除从开始删除位置到最后删除位置的所有节点，并用q暂时保存，指向最后删除节点的后驱节点的指针
        for(i = 0; i < pos+num-1; i++)
        {
            q = p;
            p =p->pNext;
            free(q);
        }

        //将新的指向第一个节点的指针返回给原来创建链表分配的指向第一个节点的指针的空间
        * list = p;

        return true;
    }

    //如果开始删除的位置不是第一个节点
    //找到指向开始删除的节点的指针，以及指向其前驱节点的指针
    for(i = 0; i < pos-1; i++)
    {
        r = p;
        p = p->pNext;
    }

    //通过指向开始删除的节点的指针，删除从开始删除位置到最后删除位置的所有节点，并找到指向最后要删除节点的后驱节点的指针
    for(i = 0; i < num; i++)
    {
        q = p;
        p =p->pNext;
        free(q);
    }

    //将开始删除节点的前驱节点挂在最后要删除节点的后驱节点
    r->pNext = p;

    return true;
}

int length_linklist(PNODE list)
{
    int len = 0;
    PNODE p = list;

    while (p)
    {   
        len++;
        p = p->pNext;
    }

    return len;    
}

void traverse_linklist(PNODE list)
{
    PNODE p = list;

    while (p)
    {
        printf("%d ", p->data);
        p = p->pNext;
    }

    printf("\n");

    return;    
}