# (C language) single linked list experiment

1. (1): write a program to establish a single linked list and output all data elements in the single linked list one by one.

Implementation code:

```#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int data;
struct node *next;
printf("Please enter the data elements in the single linked list (input)-1 Do not process when entering (end):\n");
int x;
scanf("%d",&x);
while (x != -1){
s->data = x;
p->next = s;
p = s;
scanf("%d",&x);
}
p->next = NULL;
};
if (t == NULL){
printf("The single linked table is empty!\n");
}
while(t != NULL){
printf("%d ",t->data);
t = t->next;
}
}
int main(){
printf("All elements in the single linked list are:");
return 0;
}
```

Operation results:

analysis:

The time complexity and space complexity of the functions used to output all elements in the single linked list of the leading node in the program are linear order O (n).

(2) : insert a new node x into the incrementally ordered single linked list to maintain the order of the single linked list.
Problem solving ideas: first find the insertion position, and then perform the insertion operation; Starting from the first node, find the first node greater than the value of the new node, that is, the insertion position; Then insert a new node before the found node; Note that the insertion operation can be completed only when the pointer of the node is reserved before the insertion position.

Implementation code:

```#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int data;
struct node *next;
printf("Please enter the data elements in the single linked list (input)-1 Do not process when entering (end):\n");
int x;
scanf("%d",&x);
while (x != -1){
s->data = x;
p->next = s;
p = s;
scanf("%d",&x);
}
p->next = NULL;
};
if (t == NULL){
printf("The single linked table is empty!\n");
}
while(t != NULL){
printf("%d ",t->data);
t = t->next;
}
}
p->data = x;
}
while (q != NULL && q->next != NULL){
if (x >= q->data && x < q->next->data){
p->next = q->next;
q->next = p;
}
q = q->next;
}
q->next = p;
p->next = NULL;
}
int main(){
printf("All elements in the single linked list are:");
printf("\n Please enter the data field of the new node you want to insert:");
int x;
scanf("%d",&x);
printf("After inserting a new node, all elements in the single linked list are:");
SearchAndInsert(l,x);
return 0;
}
```

Operation results:

analysis:

The time complexity and space complexity of the SearchAndInsert function used to insert according to the problem-solving idea in the program are linear order O (n).

(3) : write the sub function to realize the local inversion of the leading node single linked list, and write the main function test results.

Let's talk about how I implement inversion:
(the method is not the only one. If there are good methods, please add them.)

``` /*
The basic idea is to put one node at a time behind the head node in order
If the elements in the input single linked list are 3, 4, 5, 6, 7, 0, that is:
The original single linked list is: head - > 3 - > 4 - > 5 - > 6 - > 7 - > 0 - > null, then:
After the first cycle, the single linked list becomes: head - > 4 - > 3 - > 5 - > 6 - > 7 - > 0 - > null
After the second cycle, the single linked list becomes: head - > 5 - > 4 - > 3 - > 6 - > 7 - > 0 - > null
After the third cycle, the single linked list becomes: head - > 6 - > 5 - > 4 - > 3 - > 7 - > 0 - > null
After the fourth cycle, the single linked list becomes: head - > 7 - > 6 - > 5 - > 4 - > 3 - > 0 - > null
After the fifth cycle, the single linked list becomes: head - > 0 - > 7 - > 6 - > 5 - > 4 - > 3 - > null
To sum up, inversion is successfully realized.
*/
```

Implementation code:

```#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int data;
struct node *next;
printf("Please enter the data elements in the single linked list (input)-1 Do not process when entering (end):\n");
int x;
scanf("%d",&x);
while (x != -1){
s->data = x;
p->next = s;
p = s;
scanf("%d",&x);
}
p->next = NULL;
};
if (t == NULL){
printf("The single linked table is empty!\n");
}
while(t != NULL){
printf("%d ",t->data);
t = t->next;
}
}
if (p == NULL){
}
q = p->next;
while (p->next != NULL) {
p->next = q->next;
do{
q = q->next;
}while(q != p->next);
}
}
int main(){
printf("Before inversion,All elements in the single linked list are:");
printf("\n After inversion,All elements in the single linked list are:");
return 0;
}

```

Operation results:

analysis:

In this program, the time complexity of the local inverse sub function of the leading node single linked list is square order O (n) ²)， The space complexity is linear order O (n).

2. It is known that the pointers LA and LB respectively point to the first element of the two headless single linked lists. It is required to compile an algorithm to delete a total of len elements from the i-th element in the table LA and insert them before the j-th element in the table lb.

Implementation code:

```#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int data;
struct node *next;
printf("Please enter the data elements in the single linked list (input)-1 Do not process when entering (end):\n");
int x;
scanf("%d",&x);
if (x != -1){
p->data = x;
}else{
p = NULL;
}
scanf("%d",&x);
while (x != -1){
s->data = x;
p->next = s;
p = s;
scanf("%d",&x);
}
p->next = NULL;
};
if (t == NULL){
printf("The single linked table is empty!\n");
}
while(t != NULL){
printf("%d ",t->data);
t = t->next;
}
}
int j = 1;
while ((p->next != NULL)&&(j < i)){
p = p->next;
j++;
}
if (j == i){
return p;
}else{
return NULL;
}
}
linklist *p = LA,*q = LB,*m = NULL,*r = NULL,*s = NULL,*t = NULL;
if (i <= 0 || j <= 0 || len <= 0){
printf("Unable to delete and insert!");
return NULL;
}
m = Get(p,i-1);
if (m != NULL){
while (len > 0){
s = m->next;
m->next = s->next;
free(s);
len--;
}
}else{
printf("Single linked list LA Section in i Nodes do not exist!");
return NULL;
}
while (m->next != NULL){
m = m->next;
}
t = Get(q,j-1);
if (t != NULL){
m->next = t->next;
t->next = LA;
}else{
printf("Single linked list LB Section in j Nodes do not exist!");
return NULL;
}
return LB;
}
int main(){
int i,j,len;
printf("Single linked list LA All elements in are:");
printf("\n Single linked list LB All elements in are:");
printf("\n Please enter i，j and len Value of:\n");
scanf("%d %d %d",&i,&j,&len);
printf("From single linked list LA Deleted from page%d Elements in total%d Elements,Insert into single linked list LB pass the civil examinations%d Before the first element.",i,len,j);
LB = DeleteAndInsert(LA,LB,i,j,len);
printf("\n After the delete and insert operations are completed, the single linked list LB All elements in are:");