题目描述
给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该结点。
思路分析
一般我们删除单链表中的节点是需要遍历链表，找到要删除节点的前一个元素，但是那样的时间复杂度为O(n)，要在O(1)的时间内删除给出的节点，我们可以将删除节点p的下一个结点的值赋给p ，而我们只要删除p的下一个结点就可以了，同时我们还要注意边界值：
- 要删除的节点p是尾结点，
- 要删除的链表中只有一个节点 等特殊情况
测试用例
- 功能测试（多个结点链表，删除头结点、中间结点和尾结点；单个结点链表）
- 特殊测试（头结点或删除结点为null）
## Java代码
public class Offer18_01 {
public static void main(String[] args) {
System.out.println("****功能测试***");
test1();
System.out.println("***仅有一个节点元素的单链表测试***");
test2();
System.out.println("***特殊输入测试****");
test3();
}
public static ListNode deleteNodeInList(ListNode pHead, ListNode pdelNode) {
return Solution1(pHead, pdelNode);
}
/**
* 如果要删除的节点是中间节点，我们可以直接将它后面的一个节点的值赋给它， 而要删除的节点就变成了它后面的一个节点，
* 要考虑删除节点是尾结点，和链表中只有一个节点的情况
*
* @param pHead
* @param pdelNode
* @return
*/
private static ListNode Solution1(ListNode pHead, ListNode pdelNode) {
if (pHead == null || pdelNode == null) {
return pHead;
}
if (pdelNode.next != null) {// 要删除的节点在链表中间位置
ListNode p = pdelNode.next;
pdelNode.val = p.val;
pdelNode.next = p.next;
p = null;
} else if (pHead.next == pdelNode) {// 链表只有一个结点
pHead.next = pdelNode.next;
pdelNode = null;
} else {// 链表中有多的节点，要删除的节点是尾结点
ListNode p = pHead;
while (p.next != pdelNode) {// 搜寻pdelNode的前一个节点
p = p.next;
}
p.next = pdelNode.next;
pdelNode = null;
}
return pHead;
}
/**
* 功能测试
*/
private static void test1() {//
System.out.println("(不加头结点)有三个节点元素的单链表");
ListNode node3 = new ListNode(9, null);
ListNode node2 = new ListNode(2, node3);
ListNode node1 = new ListNode(4, node2);
ListNode pHead = new ListNode(-1, node1);// 头结点
System.out.println("删除之前");
printListNode(pHead);
System.out.println("删除之后--->");
deleteNodeInList(pHead, node2);
printListNode(pHead);
}
private static void test2() {//
System.out.println("(不加头结点)仅有一个节点元素的单链表");
ListNode node1 = new ListNode(4, null);
ListNode pHead = new ListNode(-1, node1);// 头结点
System.out.println("删除之前");
printListNode(pHead);
System.out.println("删除之后-->");
deleteNodeInList(pHead, node1);
printListNode(pHead);
}
/**
* 特殊输入测试
*/
private static void test3() {//
System.out.println("(不加头结点)有三个节点元素的单链表");
ListNode node3 = new ListNode(9, null);
ListNode node2 = new ListNode(2, node3);
ListNode node1 = new ListNode(4, node2);
ListNode pHead = new ListNode(-1, node1);// 头结点
System.out.println("删除之前");
printListNode(pHead);
System.out.println("删除之后(传入参数为null，null)--->");
deleteNodeInList(null, null);
printListNode(pHead);
}
/**
* 打印链表
*
* @param pHead
*/
private static void printListNode(ListNode pHead) {
ListNode p = pHead.next;
while (p != null) {
System.out.print(p.val + " ");
p = p.next;
}
System.out.println();
}
}