这是牛客网刷题记录专栏第一篇博文，先给大家简单介绍一下牛客网，牛客网是一个集笔面试系统、题库、课程教育、社群交流、招聘内推于一体的优质网站，牛客网题库中包含几万道题目，注重通过边学边练的模式揽获编程人员的喜爱

牛客网干净整洁的界面，人性化的布局，高质量的题库题解，丰富的大厂面试题，让我想把它分享给大家，推荐大家来牛客网刷题，链接我就放在这了有需要自取👉点击开始刷题

小Tips：注册完之后，不用填信息直接点X，开启刷题之旅~

---

链表

🔥1.牛牛的单向链表

👌描述

牛牛从键盘输入一个长度为 n 的数组，问你能否用这个数组组成一个链表，并顺序输出链表每个节点的值。

输入描述：
第一行输入一个正整数 n ，表示数组的长度

输出描述：
制作一个链表然后输出这个链表的值

示例1

输入：4
		   5 4 2 1
输出：5 4 2 1
1
2
3

说明：
请实现链表后再遍历输出结果！

👌代码

#include
using namespace std;
struct list{
    int num;
    struct list*next;
};
int main()
{
    int n;
    cin>>n;
   struct list *head;
    head=(list*)malloc(sizeof(list));
    head->next=NULL;
    list *tmp1=head;
    for(int i=0;i<n;i++)
    {
     list *tmp = (list*)malloc(sizeof(list));
        cin >> tmp->num;    //节点输入
         
        tmp1->next=tmp;
        tmp1 = tmp1->next;
        //tmp1 = tmp;
        tmp->next=NULL;   
    }
     tmp1 =head->next;
    while(tmp1 !=NULL)
    {
        cout << tmp1->num << " ";
        tmp1 = tmp1->next;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

👌题解

要注意两个地方：

1. 平时对单链表进行遍历往往是从前往后遍历
2. 输入样例的顺序和遍历的顺序是一样的，这就要求我们使用尾插法创建单链表

---

🔥2.牛牛的单链表求和

👌描述

牛牛输入了一个长度为 n 的数组，他想把这个数组转换成链表，链表上每个节点的值对应数组中一个元素的值，然后遍历链表并求和各节点的值

输入描述：
第一行输入一个正整数 n ，表示数组的长度。
第二行输入 n 个正整数，表示数组中各个元素的值

输出描述：
把数组转换成链表然后对其求和并输出这个值

示例1

输入：
5
5 2 3 1 1
输出：
12
1
2
3
4
5

👌代码

#include
#include
typedef int DataType;
typedef struct linklist
{
	DataType data;
	struct linklist* next;
}LinkList;
LinkList* InitList()
{
	LinkList* head;
	head = (LinkList*)malloc(sizeof(LinkList));
	head->next=NULL;
	return head;
}
void CreatLinkL(LinkList *head,int n)
{
	LinkList* s;
	LinkList* last;
	last = head;
	int i = 0;
	for (i = 0; i < n; i++)
	{
		s = (LinkList*)malloc(sizeof(LinkList));
		scanf("%d", &s->data);
		s->next = NULL;
		last->next = s;
		last = s;
	}
}
void get_sum(LinkList* head)
{
	LinkList* p;
	int sum = 0;
	p = head->next;
	while (p != NULL)
	{
		sum += p->data;
		p = p->next;
	}
	printf("%d", sum);
}
int main()
{
	LinkList* s;
	s = InitList();
	int n = 0;
	scanf("%d", &n);
	CreatLinkL(s, n);
	get_sum(s);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

👌题解

这个单链表求和用头插法和尾插法都可以，然后遍历单链表求和就ok

---

🔥3.牛牛的双链表求和

👌描述

牛牛输入了两个长度相同的数组分别是 a 和 b ，然后把数组 a 和 b 转换成链表 a 和链表 b 。把链表 a 中的全部值按顺序加到链表 b 中

输入描述：
第一行输入一个正整数 n ，表示数组的长度。
第二行和第三行分别输入 n 个正整数，表示数组 a 和 数组 b 的值

输出描述：
把数组 a 和数组 b 转换成链表，然后把链表 a 中的值加到链表 b 中，然后输出加和后的链表

示例1

输入：
5
5 4 2 1 3
2 4 5 8 9
输出：
7 8 7 9 12
1
2
3
4
5
6

👌代码

#include 

//单向循环链表
typedef struct node
{
    int data;
    struct node *next;
}node;

//创建链表b头节点
node *add_head()
{
    node *Head = (node *)malloc(sizeof(node));
    if(Head == NULL)
        return NULL;
    Head->next = Head;
    return Head;     
}

//尾插法
void add_node(node *Head,int data)
{
    node *new = (node*)malloc(sizeof(node));
    if(new == NULL)
        return;
    //节点成员赋值
    new->data = data;
    new->next = NULL;
    //链接
    
        node *pT = NULL;
        for(pT = Head;pT->next != Head;pT = pT->next);
        
        new->next = pT->next;
        pT->next = new;
}



//输出链表
void output(node *Head)
{
    if(Head->next == Head)
        return;
    node *pT = Head->next;
    while(pT != Head)
    {
        printf("%d ",pT->data);
        pT = pT->next;
    }
}

int main(void)
{
    node *Head = add_head();//链表头节点
    int n,i,j;
    scanf("%d",&n);
    int arr[n];
    int brr[n];
    
    //将键盘键入的数据存放到数组中
    for(i = 0;i < n;i++)
        scanf("%d",&arr[i]);
    for(i = 0;i < n;i++)
        scanf("%d",&brr[i]);
    //将数据插入链表
    for(j = 0;j < n;j++)
        add_node(Head, arr[j]+brr[j]);
    
    
    output(Head);
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

👌题解

创建一个链表的头结点，用尾插法将键盘键入的数据存放到数组中，然后再将数据插入链表

---

🔥4.牛牛的链表添加节点

👌描述

牛牛输入了一个长度为 n 的数组，他把这个数组转换成链表并在第 i 个节点的后面添加一个值为 i 的新节点

输入描述：
第一行输入两个正整数分别是 n 和 i ，表示数组的长度、需要添加节点的位置和节点的值
第二行输入 n 个正整数表示数组中每个元素的值。

输出描述：
把数组转换成链表并在第 i 个节点后的添加一个新节点值，新节点的值是 i

示例1

输入：
5 3
5 4 8 6 3
输出：
5 4 8 3 6 3
1
2
3
4
5

👌代码

#include
typedef struct link{
    int elem;
    struct link *next;
}link,*linklist;
int main(){
    int n,i,j;
    scanf("%d %d",&n,&i);
    int a[n];
    link *p=(link*)malloc(sizeof(link));
    link *temp=p;
    for(j=0;j<n;j++){
        scanf("%d",&a[j]);
    }
    for(j=0;j<i;j++){//插入前面的
        link *s=(link*)malloc(sizeof(link));
        s->elem=a[j];
        s->next=NULL;
        temp->next=s;
        temp=temp->next;
    }
    link *s=(link*)malloc(sizeof(link));
    s->elem=i;
    s->next=NULL;
    temp->next=s;
    temp=temp->next;
    for(j=i;j<n;j++){//插入剩下的
        link *s=(link*)malloc(sizeof(link));
        s->elem=a[j];
        s->next=NULL;
        temp->next=s;
        temp=temp->next;
    }
    temp=p;
    while(temp->next){
        temp=temp->next;
        printf("%d ",temp->elem);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

👌题解

链表添加节点相当于是新建一个将要插入的结点(其地址为NULL)，要将插入位置前的地址赋给新节点，让新节点再指向插入位置后的第一个结点，然后再让插入位置前的最后一个结点指向新结点就行了

---

链表来咯 👉点击开始刷题