C语言链表通关文牒3.0

经典链表，经典上工，经典数据结构考试

例题

创建一个链表，把偶数节点单拿出来组成一个新的链表

思路

总体

首先还是老三样，创建一个单向链表节点，创建单向链表，遍历函数（地地道道）

忘了或者不知道怎么回事的可以看我的刷题专栏，里面零基础链表开教

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

typedef struct node
{
    int n;
    struct node *next;
}NODE;

NODE *init()    //初始化链表
{
    NODE *h = (NODE*)malloc(sizeof(NODE));  //创建一个头节点（方便指示指针回到开头和整体引用），后面一切操作不改变头节点
    h->n = -1;
    h->next = NULL;

    //尾部指针
    NODE *pR = h;
    
    int val = -1;
    while(1)
    {
        printf("Enter a number(-1 to End):\n");
        scanf("%d",&val);
        if(val==-1)
        {
            break;
        }

        //先创建新节点,再往里面填数据
        NODE *new = (NODE*)malloc(sizeof(NODE));
        new->n = val;
        new->next = NULL;

        //新节点插入到链表中
        pR->next = new;
        //更新尾部指针指向
        pR = new;   //pR这个帽子被新创建的结构体抢走了,这样才能让下一个更新的再抢走帽子
        
    }
    return h;
}

void Foreach(NODE *h)
{
    NODE *pC = h->next;
    if(h == NULL)
    {
        return;
    }
    while(pC != NULL)
    {
        printf("%d ",pC->n);
        pC = pC->next;
    }
}

 然后需要创建另一个函数，函数中创建另一个开头，这个函数就是帮助我们选出偶数项节点的，并且把他们弄成一个新链表，取名就叫Select吧

函数应该是什么类型的？和init一样，还是NODE*类型的（函数类型如果是个*代表返回的是个什么类型的指针，比如char* Function就是返回一个字符串，开坑），这里我们要return一个链表，所以返回的指针类型是NODE*，括号里面要加工一个NODE*类型的变量（就是加工一个链表）

就是这样

接下来就是函数里面写什么

首先需要创建一个新链表（新头节点）

链表整活儿用什么来着？那我问你。

啊对了是脚标，链表怎么尖尖的

需要几个？那我问你。

链表2.0里面讲过想要孤立（这里挑出来也是孤立，只不过不free），一个链表里需要两个脚标，一个pC还有一个是pC的前一个取名pP（这样才能孤立），可是我们还有一个链表，为了重复操作，参考遍历函数，L链表也需要一个脚标进行尾插法操作（有脚标才方便重复操作）

让我们找偶数，怎么弄？计数器！

计数器

计数器配合取余数，可以找到偶数，或者几的倍数，是个挺重要的编程小工具 

接下来就是怎么处理偶数项了，不过先看一眼，一个if肯定不行，非偶数项也有脚标上面的操作，不然脚标就无法遍历了，所有框架应该是这样的

好，奇数就是两个脚标移动遍历，所有else后面就写出来了

接下来就是连、串（纯串子） 

首先如果pC是偶数项，pC2的下一项应该也是pC（C语言从上到下执行熬憋忘喽）

pC2->next = pC;

然后记得更新变量，这样才能在下次也可以操作

pC2 = pC;

然后是孤立，跳过pC2（哎，我跳）绿色的

pP->next = pC2->next;

然后就是pC要往后移一个（不能把pC顺走，没人要我就拿走了，这个脚标在上面链表还得用）

pC = pC->next;

接下来就是断舍离，断开pC2和后面联系

pC2->next = NULL;

再把这些操作写入循环就可以了 （别忘了循环外return l）

完整代码如下

NODE *Select(NODE *h)
{
    NODE *l = (NODE*)malloc(sizeof(NODE)); // 创建新链表的头节点
    l->n = -1;
    l->next = NULL;
    
    NODE *pC2 = l; // pC2 用于构建新链表的尾部
    NODE *pP = h; // pP 指向原始链表的头节点
    NODE *pC = h->next; // pC 指向原始链表的第一个实际节点
    
    int index = 1; // 初始化节点索引

    while (pC != NULL)
    {
        if(index%2 == 0)
        {
            pC2->next = pC;
            pC2 = pC;
            pP->next = pC2->next;
            pC = pC->next;
            pC2->next = NULL;

        }else{
            pP = pC;
            pC = pC->next;
        }
        
        index++; // 增加节点索引
    }

    return l;
}

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

typedef struct node
{
    int n;
    struct node *next;
}NODE;

NODE *init()    //初始化链表
{
    NODE *h = (NODE*)malloc(sizeof(NODE));  //创建一个头节点（方便指示指针回到开头和整体引用），后面一切操作不改变头节点
    h->n = -1;
    h->next = NULL;

    //尾部指针
    NODE *pR = h;
    
    int val = -1;
    while(1)
    {
        printf("Enter a number(-1 to End):\n");
        scanf("%d",&val);
        if(val==-1)
        {
            break;
        }

        //先创建新节点,再往里面填数据
        NODE *new = (NODE*)malloc(sizeof(NODE));
        new->n = val;
        new->next = NULL;

        //新节点插入到链表中
        pR->next = new;
        //更新尾部指针指向
        pR = new;   //pR这个帽子被新创建的结构体抢走了,这样才能让下一个更新的再抢走帽子
        
    }
    return h;
}

NODE *Select(NODE *h)
{
    NODE *l = (NODE*)malloc(sizeof(NODE)); // 创建新链表的头节点
    l->n = -1;
    l->next = NULL;
    
    NODE *pC2 = l; // pC2 用于构建新链表的尾部
    NODE *pP = h; // pP 指向原始链表的头节点
    NODE *pC = h->next; // pC 指向原始链表的第一个实际节点
    
    int index = 1; // 初始化节点索引

    while (pC != NULL)
    {
        if(index%2 == 0)
        {
            pC2->next = pC;
            pC2 = pC;
            pP->next = pC2->next;
            pC = pC->next;
            pC2->next = NULL;

        }else{
            pP = pC;
            pC = pC->next;
        }
        
        index++; // 增加节点索引
    }

    return l;
}





void Foreach(NODE *h)
{
    NODE *pC = h->next;
    if(h == NULL)
    {
        return;
    }
    while(pC != NULL)
    {
        printf("%d ",pC->n);
        pC = pC->next;
    }
}

int main()
{
    NODE *h = init();
    Foreach(h);
    NODE *l = Select(h);
    printf("\n");
    Foreach(h);
    printf("\n");
    Foreach(l);

    return 0;
}

效果

这里来个引申，上面不是说index%2==0吗，如果%n，就是第n的倍数项拿出来，也好理解，不多赘述

总结

经典文牒（折叠屏要是折了会流液体吗？）

我们有一些学到的知识

1、 *函数，返回一个类型的指针

2、计数器

3、画图思考

4、针对特定项有操作，还要思考非特定项有没有相关操作，考虑一下if else语句

以上均是本人理解，如有错误欢迎各位大佬评论区指出~