题目：给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该结点。
链表结点和函数的定义如下：
struct ListNode
{
int m_nValue;
ListNode* m_pNext;
}
void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted);
Java代码如下：
package demo;
public class Test12 {
/**
* 链表结点类
*/
public static class ListNode {
int value;
ListNode next;
}
public static ListNode deleteNode(ListNode head, ListNode toBeDeleted) {
// 如果输入参数有空值就返回头结点
if(head == null || toBeDeleted == null) {
return head;
}
// 如果删除头结点，则返回头结点的下一个结点
if(head == toBeDeleted) {
return head.next;
}
// 如果有多个结点，删除尾结点
if(toBeDeleted.next == null) {
// 从头结点开始遍历得到尾结点的前驱结点，然后删除
ListNode tmp = head;
while(tmp.next != toBeDeleted) {
tmp = tmp.next;
}
tmp.next = null;
} else {
// 有多个结点，删除中间结点
toBeDeleted.value = toBeDeleted.next.value;
toBeDeleted.next = toBeDeleted.next.next;
}
return head;
}
/**
* 打印链表中的元素值
* @param head
*/
public static void printList(ListNode head) {
while(head != null) {
System.out.print(head.value + "->");
head = head.next;
}
System.out.println("null");
}
public static void main(String[] args) {
ListNode head = new ListNode();
head.value = 1;
head.next = new ListNode();
head.next.value = 2;
ListNode middle = head.next.next = new ListNode();
middle.value = 3;
head.next.next.next = new ListNode();
head.next.next.next.value = 4;
ListNode tail = head.next.next.next.next = new ListNode();
tail.value = 5;
System.out.println("删除的结点为空：");
printList(deleteNode(head, null));
System.out.println("删除头结点：");
printList(deleteNode(head, head));
System.out.println("删除尾结点：");
printList(deleteNode(head, tail));
System.out.println("删除中间结点：");
printList(deleteNode(head, middle));
}
}
运行结果
