题目：给定单向链表的头指针和一个结点指针，定义一个函数在o(1)时间删除该结点。链表结点与函数的定义如下：
struct ListNode{
int m_nValue;
ListNode *m_pNext;
}
void DeleteNode(Listnode** pListHead, ListNode* pToBeDeleted);
思路：将要删除的结点的下一个结点的值复制到要删除的结点，删除下一个结点。如果是要删除最后一个结点，则要从头开始搜索。
测试用例：
1）功能测试（从有多个结点的链表的中间删除一个结点，从有多个结点的链表中删除头结点，从有多个结点的链表中删除尾结点，从只有一个结点的链表中删除唯一的结点）
2）特殊输入测试（指向链表头结点指针的为null指针，指向要删除的结点为null指针）
代码实现：
结点类：
package com.yyq; /**
* Created by Administrator on 2015/9/13.
*/
public class ListNode {
private int m_nValue;
private ListNode m_pNext; public ListNode(int m_nValue){
this.m_nValue = m_nValue;
} public ListNode getM_pNext() {
return m_pNext;
} public void setM_pNext(ListNode m_pNext) {
this.m_pNext = m_pNext;
} public int getM_nValue() {
return m_nValue;
} public void setM_nValue(int m_nValue) {
this.m_nValue = m_nValue;
}
}
实现类：
package com.yyq; /**
* Created by Administrator on 2015/9/13.
*/
public class DeleteNodeInList {
public static ListNode deleteNode(ListNode pListHead, ListNode pToBeDeleted){
if (null == pListHead || null == pToBeDeleted) {
return pListHead;
}
//要删除的结点不是尾结点
if (pToBeDeleted.getM_pNext()!= null){
ListNode pNext = pToBeDeleted.getM_pNext();
pToBeDeleted.setM_nValue(pNext.getM_nValue());
pToBeDeleted.setM_pNext(pNext.getM_pNext());
pNext = null;
}
//链表只有一个结点，删除头结点（也是尾结点）
else if(pListHead == pToBeDeleted){
pToBeDeleted = null;
pListHead = null;
}
//链表中有多个结点，删除尾结点
else{
ListNode pNode = pListHead;
while(pNode.getM_pNext() != pToBeDeleted){
pNode = pNode.getM_pNext();
}
pNode.setM_pNext(null);
pToBeDeleted = null;
}
return pListHead;
} public static void printList(ListNode pListHead){
if (pListHead == null)
return;
ListNode pNode = pListHead;
while(pNode!= null){
System.out.print(pNode.getM_nValue()+" ");
pNode = pNode.getM_pNext();
}
System.out.println();
}
// ====================测试代码====================
public static void Test(ListNode pListHead, ListNode pNode)
{
System.out.println("The original list is: ");
printList(pListHead);
if (null == pListHead || null == pNode) {
return ;
}
System.out.println("The node to be deleted is: " + pNode.getM_nValue());
pListHead = deleteNode(pListHead, pNode);
System.out.println("The result list is: ");
printList(pListHead);
System.out.println();
} // 链表中有多个结点，删除中间的结点
public static void Test1()
{
ListNode pNode1 = new ListNode(1);
ListNode pNode2 = new ListNode(2);
ListNode pNode3 = new ListNode(3);
ListNode pNode4 = new ListNode(4);
ListNode pNode5 = new ListNode(5);
ListNode pNode6 = new ListNode(6); pNode1.setM_pNext(pNode2);
pNode2.setM_pNext(pNode3);
pNode3.setM_pNext(pNode4);
pNode4.setM_pNext(pNode5);
pNode5.setM_pNext(pNode6); Test(pNode1, pNode3);
pNode1 = null;
} // 链表中有多个结点，删除尾结点
public static void Test2()
{
ListNode pNode1 = new ListNode(1);
ListNode pNode2 = new ListNode(2);
ListNode pNode3 = new ListNode(3);
ListNode pNode4 = new ListNode(4);
ListNode pNode5 = new ListNode(5);
ListNode pNode6 = new ListNode(6); pNode1.setM_pNext(pNode2);
pNode2.setM_pNext(pNode3);
pNode3.setM_pNext(pNode4);
pNode4.setM_pNext(pNode5);
pNode5.setM_pNext(pNode6); Test(pNode1, pNode6);
pNode1 = null;
} // 链表中有多个结点，删除头结点
public static void Test3()
{
ListNode pNode1 = new ListNode(1);
ListNode pNode2 = new ListNode(2);
ListNode pNode3 = new ListNode(3);
ListNode pNode4 = new ListNode(4);
ListNode pNode5 = new ListNode(5);
ListNode pNode6 = new ListNode(6); pNode1.setM_pNext(pNode2);
pNode2.setM_pNext(pNode3);
pNode3.setM_pNext(pNode4);
pNode4.setM_pNext(pNode5);
pNode5.setM_pNext(pNode6); Test(pNode1, pNode1);
pNode1 = null;
} // 链表中只有一个结点，删除头结点
public static void Test4()
{
ListNode pNode1 = new ListNode(1); Test(pNode1, pNode1);
} // 链表为空
public static void Test5()
{
Test(null, null);
} public static void main(String[] args){
Test1();
Test2();
Test3();
Test4();
Test5();
}
}
输出结果：
The original list is:
1 2 3 4 5 6
The node to be deleted is: 3
The result list is:
1 2 4 5 6
The original list is:
1 2 3 4 5 6
The node to be deleted is: 6
The result list is:
1 2 3 4 5
The original list is:
1 2 3 4 5 6
The node to be deleted is: 1
The result list is:
2 3 4 5 6
The original list is:
1
The node to be deleted is: 1
The result list is:
The original list is: