题目背景
 
在plist中删除p节点，时间复杂度要求O(1)
 
算法
 
因为时间复杂度为O(1)，所以常规思路遍历链表是不行的。删除节点，其实是把该节点数据域清除，已知了p节点，那么可以知道它的next节点，所以可以把p节点的下一个节点的数据域赋值给p节点数据域，再让p节点的next指向p->next->next，就实现了p节点数据域的清除，也就间接删除了p节点。
 如果p是最后一个节点，则只好遍历链表，复杂度O(n)
 只有p是最后一个节点时间复杂度才是O(n),平均时间复杂度(O(1)*(n-1) + O(n))/n = O(1)，所以该算法时间复杂度仍为O(1)
 
C代码
 
bool DeleteP(Linklist plist, Linklist p)//在plist中删除p节点，O(1)
{
	assert(plist != NULL);
	assert(p != NULL);
	if (plist == NULL || p == NULL)	
		return false;
	if (p->next != NULL)//p不是最后一个节点
	{
		//把p->next->data的值赋值给p->data,再让p->next指向下下个节点
		p->data = p->next->data;
		p->next = p->next->next;
		free(p->next);
		return true;
	}
	else//p是最后一个节点
	{
		LinkList tmp;
		for (; tmp->next->next != NULL;)
		{
			tmp = tmp->next;
		}
		tmp->next = NULL;
		free(tmp->next->next);
		return true;
	}
}

1，算法描述：在无头单链表中，删除指针p所指向的结点
 
      注意：是没有头结点的。
 
      算法思想：我们无法得到p所指结点的前驱，但是其后继是知道的，当前结点和后继结点的区别是data的不同，我们可以将p所指向结点的后继的值赋给p所指向的结点，将p所指向结点的后继删除，将该后继的后继地址赋给p的next。即
 
      q=p->next;
 
      p->data=q->data;
 
      p->next=q->next;
 
      free(q);
 
      注意这里p所指向的结点不能是最后一个结点，否则直接删除后，其前驱的next域无法置为NULL。
 
      代码如下：
 
       
#include "stdafx.h"
#include<stdio.h>
#include <malloc.h>
#define SIZE  100
#define  INCREMENT_SIZE 10
typedef struct  LNode
{
   int data;
   LNode *next;
}LNode,*LinkList;

//creat a LinkList
bool creatLinklist(LinkList&L,int n)
{
	LinkList p,q,t,s;
	L=(LNode*)malloc(n*sizeof(LNode));
	if(!L)
		return false;
	q=L;
	for(int i=1;i<=n;i++)
	{
		p=(LNode*)malloc(sizeof(LNode));
		scanf("%d",&p->data);
		L->next=p;
		L=p;
	}
	p->next=NULL;
	L=q;
	return true;
}

//delete a Node in a Linklist without headNode
bool LinkNoHeadlistDelete(LinkList &p)
{
	LinkList q;
	if(!p)
		return false;
	q=p->next;
	if(q)
	{
		p->data=q->data ;
		p->next=q->next;
		free(q);
		return true;
	}
}


void main()
{
	LinkList Llist,p,t;
	int k;
	int len;
	int elemet;
	int position;
	printf("input the number of LinkList to be created:");
	scanf("%d",&k);
	creatLinklist(Llist,k);
	printf("\n");
	t=Llist;
	for(int i=0;i<k-4;i++)
		t=t->next;// random a Node
	LinkNoHeadlistDelete(t);
	printf("output the new LinkList:\n");
	p=Llist->next;
	while(p)
	{
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
	free(Llist);
}
运行结果如下：
 

 

在双向链表存储结构中，删除p所指的结点时需修改指针的操作为
 p->next->prior=p->prior; p->prior->next=p->next;
 p->next=p->next->next;p->next->prior=p;
 p->prior->next=p;p->prior=p->prior->prior;
 p->prior=p->next->next;p->next=p->prior->prior;
 
答案：A

问题：
 只知道指针P指向一个单向非循环链表的节点，不是头节点也不是尾节点，从链表上把 P指向的节点删除…
 
思路：
 
一般的思路是要遍历链表找到节点P的前驱节点， 然后再删掉节点P， 但是这样效率不是很高， 可以换个思路， P节点的后继节点是可以在O(1) 复杂度下得到的， 可以将P的后继节点的数据复制到P节点中， 然后删掉P的后继节点， 重新接链即可…
 
实现如下：
 
temp = p->next;
 
p->data = p->next->data;
 
p->next = p->next->next;
 
delete temp;
 
或者：
 
temp=p->next;
 
p->data=temp->data;
 
p->next=temp->next;
 
delete temp;
 
这样就通过复制后面一个节点元素的值和next，然后删除后一个节点的方法，把当前p指向的节点间接地快速删除了
 
参考的原文连接：
 
http://blog.csdn.net/cnnumen/article/details/5804438
 
附加：要在链表中插入节点时，思路很简单，只需要考虑两个问题
 1.要插入的节点的next值是什么？
 2.要插入的节点的前一个节点是谁？也就是，把哪个节点的next值设置为指向当前待插入节点的指针？
 考虑好这两个问题，就能把要插入的节点链接到原来的链表中去了。要注意，一般是先要考虑，先处理待插入节点的next值，否则，可能就会导致它的next值对应的节点的指针找不到了。也就是考虑和处理顺序是先后再前。