16 if (!point || j > i)
17 {
18 puts("i不合法！");
19 }
20 else
21 {
22 temp = point;
23 prePoint->next = point->next;
24 *value = temp->data;
25 free(temp);
26 temp = NULL;
27 puts("删除成功！");
28 }
29 }
复制代码
时间复杂度依然是O(n)
复制代码
1 /*
2 5、头插法建立单链表（逆序建表）
3 从一个空结点开始，逐个把 n 个结点插入到当前链表的表头
4 */
5
6 //开始就空表，则肯定先分配结点（带头结点）
7 void createListByHead(LinkList *L, int n)
8 {
9 LinkList p = NULL;
10 int i = 0;
11 *L = (LinkList)malloc(sizeof(Node));//L指向头结点
12 (*L)->next = NULL;//空表建立
13 //头插法
14 for (i = 1; i <= n; i++)
15 {
16 p = (LinkList)malloc(sizeof(Node));//先创建要插入的结点
17 scanf("%c", &(p->data));//给结点数据域赋值 再次验证 -> 优先级高于取地址 &
18
19 while (getchar() != '\n')
20 {
21 continue;
22 }
23
24 p->next = (*L)->next;//再让插入的结点的next指针指向后继（链接的过程），注意后继不能为空（除去第一次插入）
25 //p->next = NULL;//错误
26 (*L)->next = p;//最后保证插入结点是第一个结点，把头结点和第一个结点链接起来。
27 }
28
29 printf("头插法建表成功\n");
30 }
复制代码
时间复杂度：必然是O（n），插入了n个元素
链表和顺序表存储结构不同，动态,整个可用内存空间可以被多个链表共享，每个链表无需事先分配存储容量，由
系统应要求自动申请。建立链表是动态的过程。
//如a b c d，依次头插法（头插 总是在第一个结点前插入，暨插入的结点总是作为第一个结点）到空链表里，那么完成之后是
//d c b a
下面是正序的尾插法，如图
复制代码
1 /*
2 6、尾插法建立单链表（顺序建表）
3 //对 5 算法的改进
4 */
5 //头插法算法简单，但生成的链表结点次序和输入的顺序相反。有时不太方便。
6 //若希望二者次序一致，可采用尾插法建表。该方法是将新结点顺次的插入到当前链表的表尾上，为此必须增加一个尾指针tail，
7 //使其始终指向当前链表的尾结点。
8 void createListByTail(LinkList *L, int n)
9 {
10 LinkList tail = NULL;//尾指针
11 int i = 0;
12 LinkList p = NULL;//代表前驱
13 *L = (LinkList)malloc(sizeof(Node));
14 (*L)->next = NULL;
15 tail = *L;
16
17 for (i = 1; i <= n; i++)
18 {
19 p = (LinkList)malloc(sizeof(Node));
20 //_CRTIMP int __cdecl scanf(_In_z_ _Scanf_format_string_ const char * _Format, ...);返回int，传入的参数个数
21 /*如果被成功读入，返回值为参数个数
22 如果都未被成功读入，返回值为0
23 如果遇到错误或遇到end of file，返回值为EOF*/
24 scanf("%c", &(p->data));
25 //清空输入队列的剩余的所有字符
26 while (getchar() != '\n')
27 {
28 continue;
29 }
30 //尾插操作，后继总是空的
31 p->next = NULL;
32 //链接前驱
33 tail->next = p;//万万不能写成*L->next = p;
34 //保证尾指针tail总是指向最后一个结点
35 tail = p;
36 }
37
38 printf("尾插法建表成功！ \n");
39 }
复制代码
这样操作，输入的序列和输出的序列是正序的，且时间复杂度为O（n）
复制代码
1 /*
2 7、尾插法建立有序单链表（归并链表）
3 把两个有序（非递减）链表LA LB合并为一个新的有序（非递减）链表LC(空表)
4 要求：不需要额外申请结点空间来完成
5 */
6
7 //1、比较数据域，保证有序
8 //2、尾插法思想
9 //3、不需要额外申请结点空间来完成！
10 //使用现有的内存空间，完成操作，那么可以想到用LC的头指针去指向其中某个表的头结点，内存共享
11
12 void mergeListsByTail(LinkList LA, LinkList LB, LinkList LC)
13 {
14 //因为要比较数据大小，需要两个标记指针，分别初始化为标记AB的第一个结点
15 LinkList listA = LA->next;
16 LinkList listB = LB->next;
17 //还要不开辟内存，那么内存共享，需要把表C让其他表去表示
18 LinkList listC;//声明一个标记C的指针
19 LC = LA;//比如表A。C表的头指针指向A表的头结点，做自己的头结点
20 listC = LA;//C表的标记指针需要初始化，指向A的头结点，待命
21 //接下来比较AB表数据，标记指针会顺次后移，早晚有一个先指向末尾之后的NULL，故判断是哪一个表的
22 while (listA && listB)
23 {
24 //判断数据大小,非递减
25 if (listA->data <= listB->data)
26 {
27 //则A的结点插入到C表（尾插）,单链表不可使用头指针做遍历
28 listC->next = li