1、使用动态链表

带头结点单链表的初始化

// 带头结点链表初始化
void InitList(Linklist *l) {
	*l = (Linklist)malloc(sizeof(LNode));
	(*l)->next = NULL;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data = 1;
	s->next = NULL;
	(*l)->next = s;
}

Linklist 是指向 LNode 结构体的指针类型，l 本身就是一个指针。在 InitList() 函数中，需要修改传入指针的值，让 l 指向链表的头节点（使用malloc函数开辟），因此传参时需要传递指针的地址，所以 InitList() 函数的参数定义为 LinkList *l ，l 为指向指针的指针。

为什么需要传递指针的地址

1. 修改指针的值：

• 当我们传递一个指针（如 Linklist l）给一个函数时，实际上传递的是指针的副本。
• 在函数内部对这个副本进行的任何修改都不会影响到原始指针。

2. 在函数内部分配内存：

• 在 InitList 函数中，我们需要为链表的头结点分配内存，并让传入的指针指向这块内存。
• 如果只传递指针的副本，分配的内存将无法反映到函数外部。

示例说明

假设我们有以下代码：

void InitList(Linklist l) {
    l = (Linklist)malloc(sizeof(LNode));
    // 其他初始化操作
}

int main() {
    Linklist l = NULL;
    InitList(l);
    // 此时 l 仍然是 NULL，因为在 InitList 中修改的是 l 的副本
}

在这个例子中，InitList 函数内部的 l 只是 main 函数中 l 的一个副本。即使我们在 InitList 中为 l 分配了内存，这个修改也不会影响到 main 函数中的 l。 个人理解为：在 main 函数中 l 指向某个地址，在 InitList 中对 l 的操作相当于让 l 的副本指向其他地址，而 main 函数中的 l 没有变。

正确的做法

通过传递指针的地址（即指向指针的指针），我们可以在函数内部修改原始指针的值：

void InitList(Linklist *l) {
    *l = (Linklist)malloc(sizeof(LNode));
    // 其他初始化操作
}

int main() {
    Linklist l = NULL;
    InitList(&l);
    // 现在 l 已经指向分配的内存，因为在 InitList 中修改的是 l 本身
}

个人理解：* 作为解引用操作符‌：用于获取指针指向的变量的值；让指针指向系统新开辟节点的地址。

按值查找

依次遍历查找，若找到，返回节点指针，否则返回空。

查找过程中不修改链表，因此形参传值时只传“副本”即可。

// 按值查找
LNode * GetLNode(Linklist l, int xNum) {
	LNode *r = l->next;
	while (r) {
		if (r->data == xNum) {
			return r;
		}
		r = r->next;
	}
	return NULL;
}

将 y 插入到 x 后面

// 插入节点
void Insert(Linklist l, int xNum, int yNum) {
	LNode *s, *r = GetLNode(l, xNum);
	if (r == NULL) {	// x 不存在
		return;
	}
	s = (LNode*)malloc(sizeof(LNode));
	s->data = yNum;
	s->next = r->next;
	r->next = s;
}

查询 x 后面的元素 

// 查找结点
void Find(Linklist l, int xNum) {
	LNode *r = GetLNode(l, xNum);
	if (r == NULL || r->next == NULL) {	// x 不存在或在最后一个
		printf("0\n");
	}
	else {
		printf("%d\n", r->next->data);
	}
}

删除 x 后面的元素

// 删除节点
void Delete(Linklist l, int xNum) {
	LNode *r = GetLNode(l, xNum), *s;
	if (r == NULL || r->next == NULL) {	// x 不存在或在最后一个
		return;
	}
	s = r->next;
	r->next = r->next->next;
	free(s);
}

释放内存

内存泄漏：指程序在申请内存后，无法释放已申请的内存空间，导致系统中可用的内存空间逐渐减少。

在链表操作过程中，我们会使用malloc等函数动态分配内存给每个节点。如果不在使用完链表后释放这些内存，就会造成内存泄漏。

LNode* temp;
while (l) {
	temp = l;
	l = l->next;
	free(temp);
}

完整代码

#include<stdio.h>
#include<stdlib.h>

typedef struct LNode {
	int data;
	struct LNode *next;
}LNode, *Linklist;

// 带头结点链表初始化
void InitList(Linklist *l) {
	*l = (Linklist)malloc(sizeof(LNode));
	(*l)->next = NULL;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data = 1;
	s->next = NULL;
	(*l)->next = s;
}

// 按值查找
LNode * GetLNode(Linklist l, int xNum) {
	LNode *r = l->next;
	while (r) {
		if (r->data == xNum) {
			return r;
		}
		r = r->next;
	}
	return NULL;
}

// 插入节点
void Insert(Linklist l, int xNum, int yNum) {
	LNode *s, *r = GetLNode(l, xNum);
	if (r == NULL) {	// x 不存在
		return;
	}
	s = (LNode*)malloc(sizeof(LNode));
	s->data = yNum;
	s->next = r->next;
	r->next = s;
}

// 查找结点
void Find(Linklist l, int xNum) {
	LNode *r = GetLNode(l, xNum);
	if (r == NULL || r->next == NULL) {	// x 不存在或在最后一个
		printf("0\n");
	}
	else {
		printf("%d\n", r->next->data);
	}
}

// 删除节点
void Delete(Linklist l, int xNum) {
	LNode *r = GetLNode(l, xNum), *s;
	if (r == NULL || r->next == NULL) {	// x 不存在或在最后一个
		return;
	}
	s = r->next;
	r->next = r->next->next;
	free(s);
}

int main() {
	int opNum;
	int opType, x, y;
	Linklist l = NULL;

	InitList(&l);
	scanf("%d", &opNum);
	while (opNum--) {
		scanf("%d", &opType);
		switch (opType) {
		case 1:
			scanf("%d %d", &x, &y);
			Insert(l, x, y);
			break;
		case 2:
			scanf("%d", &x);
			Find(l, x);
			break;
		case 3:
			scanf("%d", &x);
			Delete(l, x);
			break;
		default:
			break;
		}
	}

	LNode* temp;
	while (l) {
		temp = l;
		l = l->next;
		free(temp);
	}

	return 0;
}

使用动态链表最后两组测试点超时无法通过！ 

2、使用数组

数组下标表示元素，数组的值表示下一个元素。

完整代码

#include<stdio.h>

#define MAX 1000001    // 1 <= x, y <= 10^6

void Insert(int x, int y, int num[]) {
	num[y] = num[x];
	num[x] = y;
}

void Find(int x, int num[]) {
	printf("%d\n", num[x]);
}

void Delete(int x, int num[]) {
	int temp = num[x];
	num[x] = num[num[x]];
	num[temp] = -1;
}

int main() {
	int table[MAX] = {-1};    // 将数组值初始化为 -1
	int opNum, opType;
	int x, y;

	table[1] = 0;    // 开始只有元素 1，将最后一个元素的值设为 0
	scanf("%d", &opNum);
	while (opNum--) {
		scanf("%d", &opType);
		switch (opType) {
		case 1:
			scanf("%d %d", &x, &y);
			Insert(x, y, table);
			break;
		case 2:
			scanf("%d", &x);
			Find(x, table);
			break;
		case 3:
			scanf("%d", &x);
			Delete(x, table);
		default:
			break;
		}
	}

	return 0;
}

缺点：表的长度过大，占用大量内存。