1.3.7　节点的删除

因为链表中唯一能够找到节点的办法是使用上一个节点的指针，所以如果我们将某个节点直接删去，这个节点所指向的节点和它之后的所有节点都没有办法再找到了。为了解决这个问题，一般采取这样的方法：记录下要删除的节点之前的那个节点，在删除节点之前，把这个节点的指针指向要删除的那个节点的指针指向的节点。比如现在要删除图1.3所示链表中的节点t，先找到它之前的节点p，在删除t之前将p的指针指向节点c，然后删除t，这样在删除t之前，就已经把t从链表中剔除出来了，不会影响之后的节点。

图1.3

参考代码如下，其中第7行，表示将括号内指针指向的内存空间释放。记住，用new动态开辟的内存空间，一定要用delete()释放；否则，即便程序运行结束，这部分内存空间仍然不会被操作系统回收，从而成为被白白浪费掉的“内存垃圾”，这种现象称为“内存泄漏”。

 1    Link Del(Link Head,int i)                        //删除i位置上的节点
 2    {
 3      Link p=Head,t;
 4      if(i==1)                                       //如果是第一个节点
 5      {
 6        Head=Head->next;
 7        delete(p);                                   //删除Head指向的节点
 8      }
 9      else
10      {
11        int j=1;                                     //j为计数器
12        while(j<i-1 && p->next !=NULL)               //找到删除的前一个位置
13        {
14          p=p->next;
15          j++;
16        }
17        if(p->next!=NULL && j==i-1)
18        {
19          t=p->next;
20          p->next=t->next;
21        }
22        if(t!=NULL)
23          delete(t);                                 //释放节点内存空间
24      }
25      return Head;
26    }