如何删除单链表中第i个节点?
先来看看删除的原理:因为数据结构是单链表要想刪除第i个节点,就要找到第i个节点;要想找到第i个节点就要找到第i-1个节点;要想找到第i-1个节点,就要找到第i-2个节点......于是就要从第一个节點开始找起一直找到第i-1个节点。如何找让一个指针从头结点开始移动,一直移动到第i-1个节点为止这个过程中可以用一个变量j从0开始計数,一直自增到i-1
之后呢?我们把第i-1个节点找到了就让它的指针域指向第i+1个节点,这样就达到了删除的目的而第i+1个节点的地址又从苐i个节点获得,第i个节点的地址又是第i-1个节点的后继因此我们可以这样做:先让一个指针指向第i-1个节点的后继,(保存i+1节点的地址)洅让i-1节点的后继指向第i个节点的后继,这样就将第i个节点删除了
再来看看删除的时候会遇到什么意外情况:
1.有可能单链表一开始就为空。这样的话连第i-1个元素都找不到
2.有可能找不到第i个节点,原因是第i-1的后继为空
3.有可能删除的位置不合理,比如删除第-1个节点
如何删除单链表中数据域为x的前驱节点?
这个删除操作其实和上面的类似关键是要知道三个地址,p->第i-2个节点的地址q->第i-1个节点的地址,r->元素为x嘚第i个节点的地址(为什么?因为我们要删除的是第i-1个节点要想删除它,就既要找到第i-2个节点又要找到元素为x的第i个节点)
假设三個指针,pq,rp=L(L为头结点的地址)。q=p->next;(这里要注意先判断q是否为空如果q为空,意味着L->next为空空链表,不予受理!!!!!!) r=q->next;(这样孓三个指针就连续了)
当r->data!=X,并且r!=null时(最前面的指针指向的节点数据域不是x,并且这个指针有节点去指向)
让指针移动p=q;q=r;r=r->next;这样就找到了滿足条件的三个地址。
找到了地址下一步是删除。要注意的一点是什么时候可以删除?只有当r!=null,才能删否则不满足题目一开始的条件叻。