Some linked list topics written by leisure fish for others can be used or studied. Please do not copy.
First knowledge of linked list
Title Description
Given a positive integer sequence, the number is unknown, but there is at least one element. Your task is to establish a single linked list, use the linked list to store the positive integer sequence, then count the maximum and minimum values of the elements in the sequence, and calculate the sum of all elements in the sequence. The input of positive integer uses - 1 as the end flag. Note that - 1 does not count the elements in this positive integer sequence (do not count - 1).
input
A positive integer sequence. The number of elements in the positive integer sequence is unknown, but it ends with "- 1". At least one positive integer shall be entered before "- 1". The elements in the sequence range from 1 to 9999999.
output
Three positive integers, i.e. the maximum value, the minimum value and the sum of all elements. The number of test case nodes with the most data is in the order of 1000, and all integers can be stored in int type.
Note the input / output format.
sample input
1 4 99 21 50 61 32 4 -1
sample output
The maximum,minmum and the total are:99 1 272
#include<stdio.h>
#include<malloc.h>
typedef struct LNode
{
int data;
struct LNode * next;
}LNode,*LinkList;
LinkList createlist(LinkList head)
{
int temp;
LinkList p;
while(scanf("%d",&temp)!=EOF)
{
if(temp==-1) break;
p=(LinkList)malloc(sizeof(LNode));
p->data=temp;
p->next=head->next;
head->next=p;
}
return head;
}
//void ListPint(LinkList head)
//{
// LinkList p;
// p=head->next;
// while(p!=NULL)
// {
// printf("%d\n",p->data);
// p=p->next;
// }
//}
void findAndSum(LinkList head)
{
LinkList p;
p=head->next;
int min = p->data,max=p->data;
int sum=0;
while(p!=NULL)
{
if(p->data<=min)
{
min=p->data;
}
if(p->data>max){
max=p->data;
}
sum+=p->data;
p=p->next;
}
printf("The maximum,minmum and the total are:%d %d %d",max,min,sum);
}
int main()
{
int i;
LinkList head;
head=(LinkList)malloc(sizeof(LNode));
head->next=NULL;
head = createlist(head);
findAndSum(head);
}
Linked list sorting
Title Description
Given an unordered sequence composed of positive integers, the number is unknown, but there is at least one element. Your task is to establish a single linked list, use the linked list to store the positive integer sequence, and then sort the linked list so that the sorted linked list is an incremental sequence. The input of positive integer uses - 1 as the end flag. Note that - 1 does not count the elements in this positive integer sequence (do not count - 1). In the process of sorting, you can choose your own sorting algorithm (bubble sorting, selective sorting, etc.), but you must sort by modifying the pointer field of the node, not the data field of the node. After the program is completed, the space occupied by all nodes should be released.
input
A sequence of positive integers with unknown number of elements ends with "- 1", and at least one positive integer is entered before "- 1".
output
For the sorted linked list, there is a space after each element. Note that there is only a newline after the last element.
The number of test case nodes with the most data is in the order of 1000, and all integers can be stored in int type. Note the input / output format.
sample input
49 38 65 97 76 13 27 49 -1
sample output
The new list is:13 27 38 49 49 65 76 97
#include<stdio.h>
#include<malloc.h>
typedef struct LNode
{
int data;
struct LNode * next;
}LNode,*LinkList;
LinkList createlist(LinkList head)
{
int temp;
LinkList p;
while(scanf("%d",&temp)!=EOF)
{
if(temp==-1) break;
p=(LinkList)malloc(sizeof(LNode));
p->data=temp;
p->next=head->next;
head->next=p;
}
return head;
}
void ListPint(LinkList head)
{
LinkList p;
p=head->next;
printf("The new list is:");
while(p!=NULL)
{
if(p==head->next)
printf("%d",p->data);
else printf(" %d",p->data);
p=p->next;
}
}
void sortList(LinkList head)
{
LinkList p,q;
p=head->next;
while(p!=NULL){
q=p;
while(q!=NULL){
if(q->data<p->data){
int temp=p->data;
p->data=q->data;
q->data=temp;
}
q=q->next;
}
p=p->next;
}
}
int main()
{
int i;
LinkList head;
head=(LinkList)malloc(sizeof(LNode));
head->next=NULL;
head = createlist(head);
sortList(head);
ListPint(head);
}
Linked list matching
Title Description
Two unordered sequences a and B composed of positive integers are known. The number of elements in each sequence is unknown, but there is at least one element. Your task is to determine whether sequence B is a continuous subsequence of sequence a. Suppose B is "1 9 2 4 18", a is "33 64 1 9 2 4 18 7", and B is a continuous subsequence of a; Suppose B is "1 9 2 4 18", a is "33 1 9 64 2 4 18 7", and B is not a continuous subsequence of A.
requirement:
Establish two single linked lists A and B to store two positive integer sequences, and then judge whether linked list B is A continuous subsequence of linked list A according to the requirements of the topic. The input of positive integer uses - 1 as the end flag. Note that - 1 does not count the elements in this positive integer sequence (do not count - 1). Release all nodes in the linked list A and B before the end of the program.
input
Input two out of order positive integer sequences A and B in turn. The number of elements in the sequence is unknown, but each sequence has at least one element and ends with "- 1". Each sequence occupies one line.
output
If sequence B is A continuous subsequence of sequence A, output "ListB is the sub sequence of ListA.", Otherwise, output "ListB is not the sub sequence of ListA.". The number of test case nodes with the most data is in the order of 100, and all integers can be stored in int type.
Note the input / output format.
Sample input Copy
Sample 1:
5 4 3 2 1 -1
3 2 1 -1
Sample 2:
1 2 3 4 5 6 7 8 9 -1
1 2 3 4 5 6 7 8 0 -1
sample output
Sample 1:
ListB is the sub sequence of ListA.
Sample 2:
ListB is not the sub sequence of ListA.
#include<stdio.h>
#include<malloc.h>
typedef struct LNode {
int data;
struct LNode * next;
} LNode,*LinkList;
LinkList createlist(LinkList head) {
int temp;
LinkList p=head,q;
while(scanf("%d",&temp)!=EOF) {
if(temp==-1) break;
q=(LinkList)malloc(sizeof(LNode));
q->data=temp;
q->next=NULL;
p->next=q;
p=p->next;
}
return head;
}
void ansPint(int num) {
if(num==1){
printf("ListB is the sub sequence of ListA.");
}else{
printf("ListB is not the sub sequence of ListA.");
}
}
void print(LinkList head)
{
LinkList p;
p=head->next;
while(p!=NULL){
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
void judgeLists(LinkList headA,LinkList headB) {
LinkList p,q,g;
p=headA->next;
while(p!=NULL) {
q=headB->next;
if(p->data==q->data){
g=p;
while(q!=NULL&&g!=NULL){
if(g->data!=q->data) break;
g=g->next;
q=q->next;
}
if(q==NULL){
ansPint(1);
return;
}
}
p=p->next;
}
ansPint(0);
}
int main() {
int i;
LinkList headA,headB;
headA=(LinkList)malloc(sizeof(LNode));
headB=(LinkList)malloc(sizeof(LNode));
headA->next=NULL;
headB->next=NULL;
headA = createlist(headA);
headB = createlist(headB);
// print(headA);
// print(headB);
judgeLists(headA,headB);
}
Linked list exchange
Title Description
A positive integer sequence is known. The number of elements in the sequence is unknown, but there are at least two elements. Your task is to create a single linked list to store the positive integer sequence. Then exchange two arbitrarily specified segments in the linked list. The first segment is [s1,t1], and the second segment is [s2,t2]. s1,t1, s2 and t2 represent the number of nodes in the linked list. If s1 < = t1, s2 < = t2, t1 < s2, s2 must be less than or equal to the total number of nodes in the linked list. The input of positive integer uses - 1 as the end flag. Note that - 1 does not count the elements in this positive integer sequence (do not count - 1). Finally, release all nodes of the linked list.
input
Enter a positive integer sequence and end with "- 1". The number of elements in the sequence is unknown, but at least two positive integers must be entered before "- 1". Then there are four integers, namely s1, t1, s2 and t2.
output
For the new linked list after processing, there is a space after each element. Note that there is only newline after the last element.
The number of test case nodes with the most data is in the order of 100, and all integers can be stored in int type. Note the input / output format.
sample input
1 2 3 4 5 6 7 8 9 10 -1
1 1 4 7
sample output
The new list is:4 5 6 7 2 3 1 8 9 10
#include<stdio.h>
#include<malloc.h>
typedef struct LNode {
int data;
struct LNode * next;
} LNode,*LinkList;
LinkList createlist(LinkList head) {
int temp;
LinkList p=head,q;
while(scanf("%d",&temp)!=EOF) {
if(temp==-1) break;
q=(LinkList)malloc(sizeof(LNode));
q->data=temp;
q->next=NULL;
p->next=q;
p=p->next;
}
return head;
}
void print(LinkList head)
{
LinkList p;
p=head->next;
printf("The new list is:");
while(p!=NULL){
if(p==head->next){
printf("%d",p->data);
}else{
printf(" %d",p->data);
}
p=p->next;
}
}
void changeLists(LinkList head) {
LinkList p,S1,S2,T1,T2,g;
p=head;
int s1,t1,s2,t2;
scanf("%d %d %d %d",&s1,&t1,&s2,&t2);
int k=0;
while(p!=NULL){
if(k==s1-1){
S1=p;
}
if(k==s2-1){
S2=p;
}
if(k==t1){
T1=p;
}
if(k==t2){
T2=p;
}
k++;
p=p->next;
}
g=S1->next;
S1->next=S2->next;
S2->next=g;
g=T1->next;
T1->next=T2->next;
T2->next=g;
}
int main() {
int i;
LinkList head;
head=(LinkList)malloc(sizeof(LNode));
head->next=NULL;
head = createlist(head);
changeLists(head);
print(head);
}