在O（1）时间内删除某个节点:http://www.cnblogs.com/youxin/p/3294152.html
链表逆序（反转)
可以参考以前写的:4中方式逆序输出链表：http://www.cnblogs.com/youxin/archive/2012/06/01/2531000.html）
http://blog.sina.com.cn/s/blog_9599e9510101349g.html
google题目：输入一个链表的头结点，反转该链表，并返回反转后链表的头结点。链表结点定义如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
分析：这是一道广为流传的微软面试题。由于这道题能够很好的反应出程序员思维是否严密，在微软之后已经有很多公司在面试时采用了这道题。
为了正确地反转一个链表，需要调整指针的指向。与指针操作相关代码总是容易出错的，因此最好在动手写程序之前作全面的分析。在面试的时候不急于动手而是一开始做仔细的分析和设计，将会给面试官留下很好的印象，因为在实际的软件开发中，设计的时间总是比写代码的时间长。与其很快地写出一段漏洞百出的代码，远不如用较多的时间写出一段健壮的代码。
为了将调整指针这个复杂的过程分析清楚，我们可以借助图形来直观地分析。假设下图中l、m和n是三个相邻的结点：
a?b?…?l mànà…
假设经过若干操作，我们已经把结点l之前的指针调整完毕，这些结点的m_pNext指针都指向前面一个结点。现在我们遍历到结点m。当然，我们需要把调整结点的m_pNext指针让它指向结点l。但注意一旦调整了指针的指向，链表就断开了，如下图所示：
a?b?…l?m nà…
因为已经没有指针指向结点n，我们没有办法再遍历到结点n了。因此为了避免链表断开，我们需要在调整m的m_pNext之前要把n保存下来。
接下来我们试着找到反转后链表的头结点。不难分析出反转后链表的头结点是原始链表的尾位结点。什么结点是尾结点？就是m_pNext为空指针的结点。
基于上述分析，我们不难写出如下代码：
//返回的不是头结点，是第一个节点 Node* listReverse(LinkList L) { LinkList pReversedHead=NULL; LinkList p=L; LinkList prev=NULL; while(p!=NULL) { LinkList next=p->next; // if the next node is null, the currect is the end of original // list, and it's the head of the reversed list if(next==NULL) pReversedHead=p; // reverse the linkage between nodes p->next=prev; // move forward on the the list prev=p; p=next; } return pReversedHead; }
注意上面返回的不是头结点，而是第一个节点.而且由于头结点被当做一个有效的节点 ，所以上面的程序并不好。一个非常好的方法：
基本原理跟上面的类似，但是想法不同：
步骤如下:
1). 若链表为空或只有一个元素，则直接返回；
2). 设置两个前后相邻的指针p,q. 将p所指向的节点作为q指向节点的后继；
3). 重复2),直到q为空
4). 调整链表头和链表尾
示例：以逆序A->B->C->D为例，图示如下
Node* listReverse2(LinkList head) { if(head->next==NULL || head->next->next==NULL) { return head; } else { LinkList p=head->next; LinkList q=head->next->next; LinkList t=NULL; while(q!=NULL) { t=q->next;//先保留下一个node q->next=p; p=q; q=t; } head->next->next=NULL; head->next=p; return head; } }
可以看到，没有节点时或只有一个节点时，这时反转后还是一样，所有干脆返回。 这个方法最好。（参考了：
http://blog.sina.com.cn/s/blog_9599e9510101349g.html）
上面的还可以用递归，由于有了头结点，就麻烦点。下面的讲了没有头结点的递归和非递归形式：
将一个链表进行反转（没有头结点)，如原来的链表为1->2->3->4->5，经过反转之后的链表为5->4->3->2->1。
可以有非递归与递归两种方法：
1.非递归方法：
Node* reverseLinkList(Node* head)
{
Node* p1;
Node* p2 = NULL;
Node* tmp;
p1 = head;
if(p1)
p2 = p1->next;
while(p2) // 不用测试p1是否为空，如果p2不为空，p1肯定不为空，故p2与p1&&p2的布尔值一致
{
tmp = p2->next;
p2->next = p1;
p1 = p2;
p2 = tmp;
}
head->next = NULL; //把反转后的最后一个节点的next域置为NULL
head = p1;
return head;
}
2.递归方法：
Node* reverseLinkList_recursion(Node* pNode,Node*& head)
{
if(pNode == NULL || pNode->next == NULL)
{
head->next = NULL; //把反转后的最后一个节点的next域置为NULL
head = pNode;
return pNode;
}
Node* tmpNode = reverseLinkList_recursion(pNode->next,head);//返回原链表中pNode的下一个节点
tmpNode->next = pNode;
return pNode;
}
递归的方法是把当前节点pNode的后继节点集合看成一个节点，然后与当前节点倒换后继前驱关系。
这个函数的第二个参数head必须是一个指针的引用，因为在跳出递归的代码段中必须修改head的值，指向新的头结点，如果head指针作为值传递传进reverseLinkList_recursion函数，将不可改变head的值，所以必须传进引用值。