任意位置删除一个节点

设计一个Delete（position）函数，删除第position位的节点。

思路

1）重新连接删除后的链表

将第n-1位节点的next存第n+1位节点的地址，即第n位节点的next。

2）清除第n位节点在堆区的内存占用

使用 free( )。

代码实现

#include<stdio.h>
#include<stdlib.h>
struct Node{
	int data;
	struct Node* next;
};
struct Node* head;  //global
void Insert(int n){
	struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
	temp->data = n;
	temp->next = NULL;
	struct Node* temp1 = head;
	if(head == NULL){
		head = temp;
		return;
	}
	while(temp1->next != NULL){
		temp1 = temp1->next;
	}
	temp1->next = temp;
}
void Print(){
	struct Node* temp = head;
	while(temp != NULL){
		printf("%d ",temp->data);
		temp = temp->next;
	}
	printf("\n");
}
void Delete(int n){
	struct Node* temp1 = head;
	if(n==1){
		head = temp1->next;
		free(temp1);
		return;
	}
	for(int i=0;i<n-2;i++)
		temp1 = temp1->next;
	struct Node* temp2 = temp1->next;
	temp1->next = temp2->next; //temp1->next--第n-1位节点的next 
                               //temp2->next-第n+1位节点的next
	free(temp2);
}
int main(){
	head = NULL;
	Insert(2);
	Insert(4);
	Insert(6);
	Insert(5);
	Print();
	int n;
	for(int i=0;i<3;i++){
	printf("Enter the position\n");
	scanf("%d",&n);
	Delete (n);
	Print();
	}
	return 0;
}

输入/出结果

2 4 6 5
Enter the position
1
4 6 5
Enter the position
3
4 6
Enter the position
2
4