Learn-Algorithms/9 Algorithms Job Interview/2.2 链表-删除.md

#链表-删除

在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值相同的结点删除。