---

title: 2.2 链表 - 删除 tags: [链表 - 删除] ---## 2.2 链表 - 删除 tag-placeholder

在 O（1）时间内删除链表结点

题目：给定链表的头指针和一个结点指针，在 O(1) 时间删除该结点。链表结点的定义如下：

struct ListNode{
      int        m_nKey;
      ListNode*  m_pNext;
};

//函数的声明如下：
void deleteNode(ListNode* pListHead, ListNode* pToBeDeleted);

思路： 保存下一个节点的值 tmp，删除下一个节点，当前节点=tmp

删除链表中的 p 节点

只给定单链表中某个结点 p(并非最后一个结点，即 p->next!=NULL) 指针，删除该结点。

办法很简单，首先是放 p 中数据,然后将 p->next 的数据 copy 入 p 中，接下来删除 p->next 即可。

类似的还有问题：只给定单链表中某个结点 p(非空结点)，在 p 前面插入一个结点。办法类似，首先分配一个结点 q，将 q 插入在 p 后， 接下来将 p 中的数据 copy 入 q 中，然后再将要插入的数据记录在 p 中。都可以做到 0(1) 复杂度

将两链表中 data 值相同的结点删除

有双向循环链表结点定义为：

struct node{ 
  int data;
  struct node *front,*next;
};

有两个双向循环链表 A，B，知道其头指针为：pHeadA,pHeadB，请写一函数将两链表中 data 值相同的结点删除。