Niuke.com Brush Question Record || Linked List

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

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

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

---

链表

1.Niu Niu's singly linked list

描述

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

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

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

示例1

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

说明：
Please implement the linked list before traversing the output result！

代码

#include<iostream>
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. Usually traversing a singly linked list is often from front to back
2. 输入样例的顺序和遍历的顺序是一样的,This requires us to use tail interpolation to create a singly linked list

---

2.Niuniu's singly linked list summation

描述

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

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

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

示例1

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

代码

#include<stdio.h>
#include<stdlib.h>
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;
}

题解

This singly linked list summation can be done by head interpolation and tail interpolation,Then traverse the singly linked list and sum it upok

---

3.Niu Niu's double-linked list summation

描述

Niu Niu input two arrays of the same length a 和 b ,然后把数组 a 和 b 转换成链表 a 和链表 b .把链表 a All values ​​in are added to the linked list in order b 中

输入描述：
第一行输入一个正整数 n ,表示数组的长度.
Enter the second and third lines separately n 个正整数,表示数组 a 和 数组 b 的值

输出描述：
把数组 a 和数组 b 转换成链表,然后把链表 a The value in is added to the linked list b 中,Then output the linked list after the addition

示例1

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

代码

#include <stdlib.h>

//单向循环链表
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];
    
    //Store the data typed by the keyboard into an array
    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;
}

题解

Create the head node of a linked list,The data typed by the keyboard is stored in the array by tail interpolation,Then insert the data into the linked list

---

4.Add a node to Niuniu's linked list

描述

牛牛输入了一个长度为 n 的数组,He converts this array into a linked list and puts it in th i Add a value after each node i 的新节点

输入描述：
The first line of input two positive integers are n 和 i ,表示数组的长度、The position of the node and the value of the node need to be added
第二行输入 n positive integers representing the value of each element in the array.

输出描述：
Convert the array to a linked list and put it in i Add a new node value after a node,The value of the new node is i

示例1

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

代码

#include<stdio.h>
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++){
    //Insert in front
        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++){
    //Insert the rest
        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);
    }
}

题解

Adding a node to a linked list is equivalent to creating a new node to be inserted(其地址为NULL),To assign the address before the insertion position to the new node,Make the new node point to the first node after the insertion position,Then let the last node before the insertion position point to the new node

---

Here comes the chain点击开始刷题