当前位置：网站首页>C language - linked list creation - merge - delete and other common retest operations
C language - linked list creation - merge - delete and other common retest operations
2022-07-20 08:14:00 【Visual feast】
Linked list creation
The creation of linked lists is divided into head interpolation and tail interpolation , First, explain the tail interpolation
The tail interpolation
The tail interpolation method is that the order in which I create the input number is 1-2-3, Then the linked list created is 1-2-3. With L Node starting with ,L-1-NULL, Enter one element at a time , Put in NULL Location .
#include<stdio.h>
#include<malloc.h>
typedef struct node{
int data;
struct node *next;
}Lnode,*ListNode;
void out(ListNode L)
{
ListNode p=L->next;
while(p!=NULL)
{
printf("%d\n",p->data);
p=p->next;
}
}
ListNode create(ListNode &L,int k)
{
L=(ListNode)malloc(sizeof(Lnode));
int x;
ListNode r=L,p;
while(k--)
{
p=(ListNode)malloc(sizeof(Lnode));
scanf("%d",&x);
p->data=x;
r->next=p;
r=p;
}
r->next=NULL;
return L;
}
int main()
{
ListNode L;
L=create(L,5);
out(L);
}
We first need to create a structure , among typedef For the convenience of alias ,*ListNode The created object is the pointer to the structure . There is a general operation in creating linked lists , Namely r=L, Subsequent operations are all in r Conduct , You can't use it directly L, This is mainly to keep the header node unchanged , We go through r Just like a line , You can perform various operations on the linked list .
The first interpolation
The order of creating linked list input is 1-2-3, The generated linked list is 3-2-1, The initial node situation is L-NULL Insert the first node L-1-NULL, Insert the second node , The process is as follows ,2->next=L->next, This way L All the nodes behind are connected in series ,2-1-NULL, In use L->next=2, Has become a L-2-1-NULL, And so on ;
ListNode create_tail(ListNode &L)
{
L=(ListNode)malloc(sizeof(Lnode));
L->next=NULL;
int x;
scanf("%d",&x);
ListNode r=L,p;
while(x!=99)
{
p=(ListNode)malloc(sizeof(Lnode));
p->data=x;
p->next=r->next;
r->next=p;
scanf("%d",&x);
}
return L;
}
When creating a linked list , Use &L, In order to change the linked list . Here, the connection node is also used first r=L, In the face of r Various operations . Don't be direct to L operation , It is easy to make logical mistakes .
Output
Output is also divided into sequential output and reverse output .
Sequential output
Direct use p Accept L The node of , It can be traversed in turn .
void out(ListNode L)
{
ListNode p=L->next;
while(p!=NULL)
{
printf("%d\n",p->data);
p=p->next;
}
}
Output in reverse order
Use recursion , This will recurse to the last value first , And then in the output . Using the characteristics of recursion , After executing all the current code, return to the previous layer . At output . Be careful , Call this function to pass L->next. Because the beginning node L->data We don't pass in values
void out_re(ListNode L)
{
if(L->next!=NULL)
out_re (L->next);
printf("%d",L->data);
}
out_re（L->next）
The combination of two incrementally ordered sequences based on linked list
for example ,L1-1-3-5-7-9-NULL ,L2-2-4-6-8-10-NULL After the merger is L1-1-2-3-4-5-6-7-8-9-10-NULL. This operation of merging two linked lists . The whole idea is simple , It's about putting L1 Empty . Then concatenate the smallest value in sequence . As long as one of the linked lists is traversed , There is no need to judge the size of the remaining linked list when traversing it alone . Be sure to point the pointer of the tail list to NULL
ListNode Union_up(ListNode L1,ListNode L2,int k1,int k2)
{
ListNode p=L1->next,q=L2->next;
L1->next=NULL;
ListNode m=L1;
while(k1>0&&k2>0)
{
if(p->data<=q->data)
{
m->next=p;
m=p;
p=p->next;
--k1;
}
else
{
m->next=q;
m=q;
q=q->next;
--k2;
}
}
if(k1>0)
{
while(k1--)
{
m->next=p;
m=p;
p=p->next;
}
}
else
{
while(k2--)
{
m->next=q;
m=q;
q=q->next;
}
}
m->next=NULL;
return L1;
}
The intersection of two sets based on linked list
Find the intersection of two incremental linked lists , Both linked lists are traversed from the beginning , Who is younger, who goes back . If equal, connect them together , Be sure to note that at this time, both linked lists should go backward , Once a linked list is traversed, there will be no intersection .
ListNode union_2(ListNode L1,ListNode L2,int k1,int k2)
{
ListNode p=L1->next,q=L2->next;
L1->next=NULL;
ListNode m=L1;
while(k1>0&&k2>0)
{
if(p->data==q->data)
{
m->next=p;
m=p;
p=p->next;
q=q->next;
--k1;
--k2;
}
else if(p->data<q->data)
{
p=p->next;
k1--;
}
else
{
q=q->next;
k2--;
}
}
m->next=NULL;
return L1;
}
Reversal of linked list
Traverse the linked list from scratch , Combined with the idea of head insertion , Insert while reading . In this way, the reversal of the linked list can be realized ,
ListNode reserve(ListNode &L)
{
ListNode p=L->next,r;
L->next=NULL;
while(p!=NULL)
{
r=p;
p=p->next;
r->next=L->next;
L->next=r;
}
return L;
}
Delete the nodes in the linked list that meet the interval value
such as L-1-2-3-4-5-NULL, Delete 2-4 Values in range . become L-1-5-NULL, Deleting a node usually requires two pointers , One is p=L, the other one q=L->next; When you want to delete a node . Just directly p->next=q->next Just skip this node .
ListNode del_range(ListNode &L,int mink,int maxk)
{
ListNode p=L,q=L->next;
while(q!=NULL)
{
if(q->data>=mink&&q->data<=maxk)
{
p->next=q->next;
q=q->next;
}
else
{
q=q->next;
p=p->next;
}
}
p->next=NULL;
return L;
}
Find the penultimate... In the linked list K Nodes
The simplest and most effective way is to traverse once to know the length , Then directly traverse to the specified location for the second time .
int length(ListNode L)
{
ListNode p=L->next;
int len=1;
while(p->next!=NULL)
{
len++;
p=p->next;
}
return len;
}
void out_re_k(ListNode L,int k)
{
int le=length(L);
ListNode p=L->next;
le=le-k;
while(le--)
{
p=p->next;
}
printf("%d",p->data);
}
Traverse once to delete the penultimate k Nodes
At this time, three pointers are needed , In this way, you only need to traverse once to delete the specified node , Give Way q=L->next, Give Way t First traversal k Time . after q and t Nodes traverse at the same time , such t Nodes traverse to the linked list NULL The location of ,q Then it just points to the penultimate k Nodes .
ListNode del_k(ListNode L,int n)
{
ListNode p=L,q=L->next;
ListNode t=L->next;
while(n--)
{
t=t->next;
}
while(t!=NULL)
{
p=p->next;
q=q->next;
t=t->next;
}
p->next=q->next;
return L;
}
Exchange two adjacent nodes in the linked list
L-1-2-3-4-NULL After the exchange is L-2-1-4-3-NULL
L-5-2-6-3-6-NULL After the exchange is L-2-5-3-6-6-NULL
The question of this exchange is divided into two ideas in the linked list , A switching node , Is to modify the pointer of the linked list . Another direct exchange value , This function can also be realized
ListNode swap(ListNode L,int k)
{
ListNode p,q,r=L;
int n=int(k/2);
for(int i=0;i<n;i++)
{
p=r->next;
q=r->next->next;
p->next=q->next;
r->next=q;
q->next=p;
r=r->next->next;
}
return L;
}
Simple selection sorting based on linked list
The sorting of linked lists is more complicated , The simplest and most effective way is to exchange values to sort . The idea of simple selection sorting is to find the minimum value in each iteration , Sort in order .k It's the length of the list .t It is used to store the current minimum traversal position . In each iteration, the first one defaults to the minimum value .
ListNode select_up(ListNode L,int k)
{
ListNode p=L->next,q,t;
int min;
while(--k)
{
q=p->next;
min=p->data;
t=NULL;
while(q!=NULL)
{
if(q->data<min)
{
min=q->data;
t=q;
}
q=q->next;
}
if(t!=NULL)
{
t->data=p->data;
p->data=min;
}
p=p->next;
}
return L;
}
Decomposition of linked list
The values of nodes in the linked list are divided into two linked lists , The value is greater than zero in the linked list A, The value is less than zero in the linked list B, The core idea of linked list decomposition is to use the head node L, And creating a header node B, And then L Values less than zero are directly deleted and moved to B Under the linked list of .
ListNode split(ListNode L,int k)
{
ListNode B,p,q,n;
q=L;
p=L->next;
B=(ListNode)malloc(sizeof(Lnode));
B->next=NULL;
ListNode r1=B;
while(k--)
{
if(p->data<0)
{
n=p;
q->next=p->next;// The second step is to delete
p=p->next;
r1->next=n; // This step is the serial operation == The tail interpolation
r1=n;
}
else
{
q=q->next;
p=p->next;
}
}
r1->next=NULL;
return B;
}
Division of odd and even nodes
This is basically the same as the above . Just modify the judgment conditions
ListNode split_o(ListNode L,int k) k For the length
{
ListNode p,q,n,B;
B=(ListNode)malloc(sizeof(Lnode));
B->next=NULL;
ListNode r1=B;
q=L;
p=L->next;
int i=1;
while(k--)
{
if(i%2==0)
{
n=p;
q->next=p->next;
p=p->next;
r1->next=n;
r1=n;
i++;
}
else
{
q=q->next;
p=p->next;
i++;
}
r1->next=NULL;
}
return B;
}
Sort
The idea of simple selection sorting is to find the minimum value every time , from n,n-1,n-2 Find the minimum value for a row . This ensures that the final sort is in ascending order . However, it is inconvenient for the linked list to exchange positions directly , So finding the minimum value requires marking the current position .
ListNode select_up(ListNode L,int k)
{
ListNode p=L->next,q,t;
int min;
while(--k)
{
q=p->next;
min=p->data;
t=NULL;
while(q!=NULL)
{
if(q->data<min)
{
min=q->data;
t=q;
}
q=q->next;
}
if(t!=NULL)
{
t->data=p->data;
p->data=min;
}
p=p->next;
}
return L;
}
Bubble sort
ListNode up_sort(ListNode L,int k)
{
ListNode r=L,p,q;
int t=0;
while(k--)
{
q=r->next;
p=r->next->next;
while(q->next!=NULL)
{
if(q->data>=p->data)
{
t=q->data;
q->data=p->data;
p->data=t;
}
q=q->next;
p=p->next;
}
}
return L;
}
Sum of linked list
ListNode count(ListNode L1,ListNode L2,int k1,int k2)
{
ListNode r1=L1->next,r2=L2->next;
ListNode B,m;
B=(ListNode)malloc(sizeof(Lnode));
B->next=NULL;
int a=0,b=0,c=0,last=0,t=0;
while(k1--&&k2--)
{
a=r1->data;
b=r2->data;
r1=r1->next;
r2=r2->next;
t=a+b+c;
m=(ListNode)malloc(sizeof(Lnode));
if(t>=10)
{
last=t%10;
c=1;
m->data=last;
m->next=B->next;
B->next=m;
}
else
{
c=0;
m->data=t;
m->next=B->next;
B->next=m;
}
}
if(k1>0)
{
while(k1--)
{
a=r1->data;
r1=r1->next;
a=a+c;
if(a<10)
{
c=0;
m=(ListNode)malloc(sizeof(Lnode));
m->data=a;
m->next=B->next;
B->next=m;
}
else
{
c=1;
last=a%10;
m=(ListNode)malloc(sizeof(Lnode));
m->data=last;
m->next=B->next;
B->next=m;
}
}
}
else
{
while(k2--)
{
a=r2->data;
r2=r2->next;
a=a+c;
if(a<10)
{
c=0;
m=(ListNode)malloc(sizeof(Lnode));
m->data=a;
m->next=B->next;
B->next=m;
}
else
{
c=1;
last=a%10;
m=(ListNode)malloc(sizeof(Lnode));
m->data=last;
m->next=B->next;
B->next=m;
}
}
}
if(c==1)
{
m=(ListNode)malloc(sizeof(Lnode));
m->data=1;
m->next=B->next;
B->next=m;
}
return B;
}
summary
There are many general operations of linked lists , For example, you need to delete immediately p->next=q->next,q=q->next. And so on, you can divide the linked list into several small modules , If you encounter a problem, just think about it by combining small modules .
Part of the test code
#include<stdio.h>
#include<malloc.h>
#include<math.h>
typedef struct node{
int data;
struct node *next;
}Lnode,*ListNode;
ListNode create(ListNode &L)
{
L=(ListNode)malloc(sizeof(Lnode));
int x;
scanf("%d",&x);
ListNode r=L,p;
while(x!=99)
{
p=(ListNode)malloc(sizeof(Lnode));
p->data=x;
r->next=p;
r=p;
scanf("%d",&x);
}
r->next=NULL;
return L;
}
ListNode create_2(ListNode &L,int k)
{
L=(ListNode)malloc(sizeof(Lnode));
int x;
ListNode r=L,p;
while(k--)
{
p=(ListNode)malloc(sizeof(Lnode));
scanf("%d",&x);
p->data=x;
r->next=p;
r=p;
}
r->next=NULL;
return L;
}
ListNode Union(ListNode L1,ListNode L2)
{
ListNode p=L1->next;
while(p->next!=NULL)
{
p=p->next;
}
p->next=L2->next;
return L1;
}
ListNode up_sort(ListNode L,int k)
{
ListNode r=L,p,q;
int t=0;
while(k--)
{
q=r->next;
p=r->next->next;
while(q->next!=NULL)
{
if(q->data>=p->data)
{
t=q->data;
q->data=p->data;
p->data=t;
}
q=q->next;
p=p->next;
}
}
return L;
}
ListNode Union_up(ListNode L1,ListNode L2,int k1,int k2)
{
ListNode p=L1->next,q=L2->next;
L1->next=NULL;
ListNode m=L1;
while(k1>0&&k2>0)
{
if(p->data<q->data)
{
m->next=p;
m=p;
p=p->next;
--k1;
}
else if(p->data==q->data)
{
m->next=p;
m=p;
p=p->next;
q=q->next;
--k1;
--k2;
}
else
{
m->next=q;
m=q;
q=q->next;
--k2;
}
}
if(k1>0)
{
while(k1--)
{
m->next=p;
m=p;
p=p->next;
}
}
else
{
while(k2--)
{
m->next=q;
m=q;
q=q->next;
}
}
m->next=NULL;
return L1;
}
ListNode swap(ListNode L,int k)
{
ListNode p,q,r=L;
int n=int(k/2);
for(int i=0;i<n;i++)
{
p=r->next;
q=r->next->next;
p->next=q->next;
r->next=q;
q->next=p;
r=r->next->next;
}
return L;
}
ListNode union_2(ListNode L1,ListNode L2,int k1,int k2)
{
ListNode p=L1->next,q=L2->next,C;
C=(ListNode)malloc(sizeof(Lnode));
C->next=NULL;
ListNode m=C;
while(k1>0&&k2>0)
{
if(p->data==q->data)
{
m->next=p;
m=p;
p=p->next;
q=q->next;
--k1;
--k2;
}
else if(p->data<q->data)
{
p=p->next;
k1--;
}
else
{
q=q->next;
k2--;
}
}
m->next=NULL;
return L1;
}
ListNode del_abs_same(ListNode L,int k1)
{
ListNode p=L->next,q=L;
int a[100]={
0};
while(p!=NULL)
{
a[abs(p->data)]=1;
p=p->next;
}
p=L->next;
while(k1--)
{
if(a[abs(p->data)]==1)
{
a[abs(p->data)]=0;
p=p->next;
q=q->next;
}
else
{
q->next=p->next;
p=p->next;
}
}
return L;
}
ListNode union_set(ListNode L1,ListNode L2,int k1,int k2)
{
ListNode p=L1->next,q=L2->next;
L1->next=NULL;
ListNode m=L1;
while(k1>0&&k2>0)
{
if(p->data<q->data)
{
m->next=p;
m=p;
p=p->next;
--k1;
}
else if(p->data>q->data)
{
q=q->next;
--k2;
}
else
{
p=p->next;
q=q->next;
--k1;
--k2;
}
}
while(k1)
{
m->next=p;
m=p;
p=p->next;
--k1;
}
m->next=NULL;
return L1;
}
ListNode create_tail(ListNode &L)
{
L=(ListNode)malloc(sizeof(Lnode));
L->next=NULL;
int x;
scanf("%d",&x);
ListNode r=L,p;
while(x!=99)
{
p=(ListNode)malloc(sizeof(Lnode));
p->data=x;
p->next=r->next;
r->next=p;
scanf("%d",&x);
}
return L;
}
ListNode reserve(ListNode &L)
{
ListNode p=L->next,r;
L->next=NULL;
while(p!=NULL)
{
r=p;
p=p->next;
r->next=L->next;
L->next=r;
}
return L;
}
ListNode add(ListNode &L,int value)
{
ListNode p=L->next,s;
s=(ListNode)malloc(sizeof(Lnode));
s->data=value;
while(p->next!=NULL)
{
p=p->next;
}
p->next=s;
p=s;
p->next=NULL;
return L;
}
int length(ListNode L)
{
ListNode p=L->next;
int len=1;
while(p->next!=NULL)
{
len++;
p=p->next;
}
return len;
}
void out(ListNode L)
{
ListNode p=L->next;
while(p!=NULL)
{
printf("%d\n",p->data);
p=p->next;
}
}
ListNode insert(ListNode &L,int i,int value)
{
ListNode p=L,s;
i=i-1;
while (i&&p!=NULL)
{
p=p->next;
i--;
}
s=(ListNode)malloc(sizeof(Lnode));
s->data=value;
s->next=p->next;
p->next=s;
return L;
}
ListNode del_range(ListNode &L,int mink,int maxk)
{
ListNode p=L,q=L->next;
while(q!=NULL)
{
if(q->data>=mink&&q->data<=maxk)
{
p->next=q->next;
q=q->next;
}
else
{
q=q->next;
p=p->next;
}
}
p->next=NULL;
return L;
}
ListNode del(ListNode &L,int i)
{
ListNode p=L,q=L->next;
while(i-1)
{
i--;
q=q->next;
p=p->next;
}
p->next=q->next;
free(q);
return L;
}
void out_re(ListNode L)
{
if(L->next!=NULL)
out_re (L->next);
printf("%d",L->data);
}
void out_re_k(ListNode L,int k)
{
int le=length(L);
ListNode p=L->next;
le=le-k;
while(le--)
{
p=p->next;
}
printf("%d",p->data);
}
//int main()
//{
// ListNode L1,L2;
// printf(" Enter the first linked list :");
// L1=create(L1);
// printf(" Please enter the first linked list :");
// L2=create(L2);
// L1=Union(L1,L2);
//
// out(L1);
//
//}
// int main()
// {
// ListNode L1,L2;
// printf(" Enter the length of the two linked lists ");
// int k1,k2;
// scanf("%d",&k1);
// scanf("%d",&k2);
// printf(" Please enter the first linked list :");
// L1=create_2(L1,k1);
// printf(" Please enter the second linked list :");
// L2=create_2(L2,k2);
// L1=union_set(L1,L2,k1,k2);
// out(L1);
// }
int main()
{
ListNode L;
L=create_2(L,5);
L=up_sort(L,5);
out(L);
} Insert a code chip here
边栏推荐
- nodejs面经
- An open source web drawing board is really convenient
- Compiler division optimization
- JWT、CAS、Oauth2、SAML单点登录SSO对比分析
- CacheManager - 用 C＃ 编写的 .NET 的开源缓存抽象层
- Codeforces 429E 2-SAT
- 那些年微信支付踩过的坑
- There is a problem that the picture cannot be found after the jar package is printed on the swing form
- three. JS create distortion slider
- .NET Core 使用 ImageSharp 生成图片
猜你喜欢
2021水下声学目标检测总结-Rank2
. Net core uses imagesharp to generate pictures
Compiler remainder optimization
pytorch 目标检测竞赛（一）数据分析
![[signal conditioning] sharing practical experience of building CE amplifier with](/img/d2/e37f084d57845f6d5b7744c0d28e52.png)
[signal conditioning] sharing practical experience of building CE amplifier with "crystal triode"
![Rlib learning [2] --env definition + env rollout](/img/6e/5109b7e95d07dce79fe40bec150d53.png)
Rlib learning [2] --env definition + env rollout
微擎系统在生产运行异常
pytorch yolo4训练任意训练集
那些年微信支付踩过的坑
开发提测标准（简易版）
随机推荐
The gratitude and resentment between the four swordsmen and code review: "abandon all chaos" to "prodigal son returns"
c语言-链表二叉树-创建-遍历-求高度等复试常见问题
Input text to automatically generate images, it's so fun!
Mongo sort exceeds maximum memory error
MFC和ATL共享的选件类
Selnium get JS content
CyclicBarrier
Redis地理算法GEO解析和应用
Jetpack compose比xml优秀的地方
Firewall port forwarding
This free code snippet manager is open source!
Nodejs学习
Use Wireshark's common filtering commands
SpiderPi便捷操作手册
pytorch mmdetection2.0安装训练测试(coco训练集)
Mongodb亿级别数据操作
SQL 时间拼接问题，系统自动截断的拼接复原
关于clean时，IDE提示Some problems were encountered while building the effective model for
The micro engine system runs abnormally in production
Upgrade the pit stepped in php8