单链表的插入操作（全）

1 在指定位序插入数据
第一步
主要执行操作：查找
先查找所要插入位置的前一个元素
具体方法：根据链表的特点-每一个节点都需要一个数据域和指针域
所以只需从头节点遍历到所要插入数据的的前一个节点即可

后面的showList函数也用的这种方法
第二步
主要执行操作：插入
创建一个新节点s（名称无所谓）给s的数据域赋值为e（e即你所要插入的数据）代码如下演示

2 在指定位置后插入数据
第一步和1操作只有一个地方不一致，只需把查找的代码中i-1 变为 i 即可
第二步
和1的第二部操作一致

3 在指定位置前插入数据
第一种方法
可以根据每个节点都有一个指针域来处理
即通过从头节点遍历到所要插入节点的前一个节点
时间复杂度为O(n) 问题规模n为插入的位序
第二种方法
我们换一种思路即交换所要插入节点和所要插入节点前的节点的值
即可完成插入时间复杂度为O(1) 比第一种更省时，方便，简洁试试

代码如下：

s->next = p->next;
   p->next = s; // 新节点s连到p节点之后
   s->data = p->data; // 利用交换数据来插入节点
   p->data = e;

add:

如果想直接在节点插入的话把上面那部分代码修改下面代码即可：

int ListInsertPriorNode(LNode* p, int e) // 在指定元素前面进行插入操作
{
   if (p == NULL)
   {
       cout << "你所插入的节点不存在" << endl;
       exit(0);
   }
   LNode* s = (LNode*)malloc(sizeof(LNode)); // 创建新节点s
   if (s == NULL)
   {
       cout << "内存分配失败" << endl;
       exit(0);
   }
   s->next = p->next;
   p->next = s; // 新节点s连到p节点之后
   s->data = p->data; // 利用交换数据来插入节点
   p->data = e;
   return e; // 返回插入的元素
}

完整代码如下：

#include<iostream>
#include<stdio.h> // malloc函数头文件
using namespace std;
typedef struct LNode
{
   int data; // 数据域
   LNode* next; // 节点域
}LNode,*LinkList;
void InitList_Head(LinkList& L, int n) // 初始化单链表
{
   L = (LNode*)malloc(sizeof(LNode)); // 创建节点
   if (L == NULL)
   {
       cout << "创建节点失败" << endl;
       exit(0); // 退出程序
   }
   L->next == NULL; // 链表设空
   cout << "请输入数据" << endl;
   LNode* s;
   LNode* r; // 尾指针
   r = L; // 把L赋给r
   for (int i = 1; i <= n; i++)
   {
       s = (LNode*)malloc(sizeof(LNode)); // 创建新节点s
       scanf_s("%d", &(s->data)); // 创建新节点
       r->next = s; // 尾插法初始化链表
       r = s;
   }
   r->next = NULL; //尾节点指向空节点
}
int ListInsert(LinkList& L, int i, int e) // 在指定位置上插入数据
{
   if (i < 1)
   {
       cout << "您所插入的位置不存在" << endl;
       exit(0);
   }
   LNode* p; // 指向p指向当前扫描到的节点
   int j = 0; // 当前p指向的第几个节点计数
   p = L; // L指向头结点
   while (p != NULL && j < i- 1) // 找到所插入节点i的前一个节点
   {
       p = p->next;
       j++;
   }
   if (p == NULL) // i值不合法
   {
       exit(0);
   }
   LNode* s ;
   s = (LNode*)malloc(sizeof(LNode)); // 创建新节点s
   s->data = e; // 赋值
   s->next = p->next;
   p->next = s; // 把s节点连在p节点之后
   return e; // 返回所插入的数据
}
int ListInsertNext(LinkList &L, int i, int e) // 指定节点的后插操作
{
   if (i < 1)
   {
       cout << "插入位置不合法" << endl;
       exit(0);
   }
   LNode* p; // 指向p指向当前扫描到的节点
   int j = 0; // 当前p指向的第几个节点计数
   p = L; // L指向头结点
   while (p != NULL && j < i ) // 找到所插入节点i节点
   {
       p = p->next;
       j++;
   }
   if (p == NULL) // i值不合法
   {
       exit(0);
   }
   LNode* s;
   s = (LNode*)malloc(sizeof(LNode)); // 创建新节点s
   s->data = e; // 赋值
   s->next = p->next;
   p->next = s; // 把s节点连在p节点之后
   return e; // 返回所插入的数据
}

int ListInsertPriorNode(LinkList& L, int i, int e)
{
   if (i < 1)
   {
       cout << "插入位置不合法" << endl;
       exit(0);
   }
   LNode* p; // 指向p指向当前扫描到的节点
   int j = 0; // 当前p指向的第几个节点计数
   p = L; // L指向头结点
   while (p != NULL && j < i) // 找到所插入节点i节点
   {
       p = p->next;
       j++;
   }
   if (p == NULL) // i值不合法
   {
       exit(0);
   }
   LNode* s;
   s = (LNode*)malloc(sizeof(LNode)); // 创建新节点s
   s->next = p->next;
   p->next = s; // 新节点s连到p节点之后
   s->data = p->data; // 利用交换数据来插入节点
   p->data = e;
   return e; // 返回插入的元素
}
void showList(LinkList& L)
{
   LNode* p;
   p = (LNode*)malloc(sizeof(LNode)); // 创建新节点p
   p = L->next;
   while (p != NULL) // 遍历
   {
       cout << p->data << endl;
       p = p->next;
   }
}
int main()
{
   LinkList L; // 创建一个单链表
   InitList_Head(L, 5); // 表中有五个数据
   //int a = ListInsert(L,3,4); // 指定位序插入
   //cout << "插入的数据为" << a << endl;
   //int b = ListInsertNext(L, 3, 5); // 指定位序后插入
   //cout << "插入的数据为" << b << endl;
   int c = ListInsertPriorNode(L, 3, 2); // 指定位序前插入
   cout << "插入的数据为" << c << endl;
   showList(L);
}