526互联

在不知带头节点地址的情况下删除和插入一个p指针指向的节点总结

发布时间 2023-10-26 21:10:01作者: 仔仔的棒棒糖

在不知带头节点地址的情况下删除和插入一个p指针指向的节点总结 （p指向的不是第一个，也不是最后一个）A->B->C *p->B

  1. 插入(在p结点之前插入q)
    解析： 直接往p前插入q，由于没有头节点，不能遍历到p的位置，所以向p的后面插入q，在交换p、q的值
  q->next = p->next;
  p->next = q;
  swap(&p->data, &q->data);
  1. 删除
    有一个单项的链表,在没有头结点的情况下,只知道有一个指向结点B的指针p,假设这个结点B不是尾结点,删除该节点B。
    解析：要删除p指向的结点B，必须要将结点B前后的两个节点A和C连接起来，但是该单链表没有头结点，因此无法追溯到A，也就无法将A和C相连了。无法删除结点B，但我们可以删除B的后继结点C，并通过p->next = p->next->next重新将链表连接起来，而唯一丢失的是结点C的数据项data。因此，我们只需要将结点C的数据项取代结点B的数据项，然后将真正指向结点C的指针删除即可是实现将结点B删除。
    p->data = p->next->data; //p->next == C
    p->next = p->next->next;
    free(p->next)

扩展：给定链表的头指针和一个结点指针，在O(1)时间删除该结点。其实也可以用这种方式，把要删除的节点下一个的数据挪到需要删除节点里，再把下一个节点删除。