image.png

    根本用不着惊动其他结点，只需要让s->next和p->next的指针做一点改变即可。

    1. s->next = p->next;//让p的后继结点改成s的后继结点s->next = p->next;
    2. p->next = s;//再把结点s变成p的后继结点

    （如图所示）。
    image.png
    考虑一下，这两句的顺序可不可以交换？

    1. p->next=s;//如果先————此时第一句会使得将p->next给覆盖成s的地址了。
    2. s->next=p->next;//再...会怎么样？————s->next=p->next，其实就等于s->next=s，
    3. //这样真正的拥有ai+1数据元素的结点就没了上级。
    1. //次链表是单向的，从前往后，所以优先操作后继结点
    2. ListNode* newNode = (ListNode*)malloc(sizeof(SListDataType));
    3.     newNode->next = p->next;
    4.     p->next = newNode
    6. //交换顺序的话，也可以用一个指针提前将p的后继结点的地址保存，防止p的后继结点的地址在交换中覆盖掉
    7.     next = p->next;
    8.     p->next = s;
    9.     s->next = next;

    插入结点s后，链表如图所示。
    image.png

    对于单链表的表头和表尾的特殊情况，头插，尾插

    1. //头插：
    2. s->next = phead->next;
    3. phead = s;
    4. //尾插：
    5. tail->next = s

    操作是相同的，如图所示。
    image.png

    单链表第i个数据插入结点的算法思路：

    1. 声明一指针p指向链表头结点，初始化j从1开始；
    2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1；
    3. 若到链表末尾p为空，则说明第i个结点不存在；
    4. 否则查找成功，在系统中生成一个空结点s；
    5. 将数据元素e赋值给s->data；
    6. 单链表的插入标准语句s->next=p->next;p->next=s；
    7. 返回成功。

    总结：
    在使用带头结点的单链表时
    1、初始化链表头部指针需要用二级指针
    2、销毁链表需要用到二级指针
    3、插入、删除、遍历、清空结点用一级指针即可

    注意：
    如果是不带头结点的单链表，插入、删除和清空结点也需要二级指针（比如往空链表中插入一个节点时，新插入的节点就是链表的头指针，此时会改动头指针。同理，删除第一个结点和清空结点都会改动头指针）。

    1. 实现代码算法如下：
    2. /* 初始条件：顺序线性表L已存在，1 ≤ i ≤ ListLength(L)， */
    4. /* 操作结果：在L中第i个结点位置之前插入新的数据元素e，L的长度加1 */
    6. //要想对链表中结点改动的都需要使用二级指针，要不然一级指针作为形参是无能为力的
    7. //LinkList *L中L是二级指针
    8. Status ListInsert(LinkList *L, int i, ElemType e)
    9. {
    10.     int j;
    11.     //一级结点类型指针
    12.     LinkList p, s;
    14.     //这样定义的话，L是二级头指针，*L是一级头指针
    15.     //
    16.     p = *L;
    17.     j = 1;
    19.     /* 寻找第i-1个结点 */
    20.     while (p && j < i)//防止p为空，出现空指针异常              
    21.     {
    22.         p = p->next;//p是头指针,结点类型指针，p->next<=>(*L)->next是头结点的后继地址，首结点第一数据结点地址
    23.                     //所以p指向首结点
    24.                     //第一次j=1时，指向首结点的//最后一次j=i-1时，指向i-1个结点
    25.         ++j;
    26.     }
    28.     /* 第i个结点不存在 */
    29.     if (!p || j > i)
    30.         return ERROR;                      
    32.     /* 生成新结点（C标准函数） */
    33.     s = (LinkList)malloc(sizeof(Node));    
    35.     s->data = e;
    37.     /* 将p的后继结点赋值给s的后继 */s指向p的后继结点
    38.     s->next = p->next;                    
    39.     /* 将s赋值给p的后继 */p结点指向s
    40.     p->next = s;                           
    42.     return OK;
    44. }
    46. 在这段算法代码中，我们用到了C语言的mal-loc标准函数，它的作用就是生成一个新的结点，
    47. 其类型与Node是一样的，其实质就是在内存中找了一小块空地，准备用来存放数据e的s结点。