在O（1）时间删除链表结点

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        if(pHead == null){
            return null;
        }
        ListNode newNode = new ListNode(-1);
        newNode.next = pHead;
        ListNode cur = pHead;
        ListNode pre =newNode;
        while(cur !=null && cur.next != null){
            if(cur.next.val == cur.val){
                int temp = cur.val;
                while (cur != null && cur.val == temp){
                    cur = cur.next;
                }
                pre.next = cur;
            }else {
                pre = cur;
                cur = cur.next;
            }
        }
        return newNode.next;
    }
}

概念

在单向链表中删除一个节点，常规的做法无疑是从链表的头节点开始，顺序遍历查找要删除的节点，并在链表中删除该节点。我们想删除节点i, 可以从链表的头节点a 开始顺序遍历，发现节点h 的 m^pNext指向要删除的节点i, 于是我 们 可 以 把 节 点 指 向 i 的下一个节点，即节点j 。指针调整之后，我们就可以安全地删除节点i 并保证链表没有断开，如

这种思路由于需要顺序查找，时间复杂度自然就是〇( n )了。之所以需要从头开始查找，是因为我们需要得到将被删除的节点的前一个节点。在单向链表中，节点中没有指向前一个节点的指针，所以只好从链表的头节点开始顺序查找。

之前的方法

注：（a ) —个链表，（b ) 在删除节点i 之前，先从链表的头节点开始遍历到i 前面的一个节点h，把 h 的 m_pNext指向i 的下一个节点j , 再删除节点i ( c )把节点j 的内容复制覆盖节点i, 接下来再把节点i 的 m_pNext指向j 的下一个节点，再删除节点j 这种方法不用遍历链表上节点i 前面的节点。

现在的方法

如果我们把下个节点的内容复制到需要删除的节点上覆盖原有的内容，再把下一个节点

删除，那是不是就相当于把当前需要删除的节点删除了？我们还是以前面的例子来分析这种思路。我们要删除节点i，先把i 的下一个节点j 的内容复制到i,然后把i 的指针指向节点j 的下一个节点。此时再删除节点j ，其效果刚好是把节点i 删除了，

注意

上述思路还有一个问题：如果要删除的节点位于链表的尾部，那么它就没有下一个节点，怎么办？我们仍然从链表的头节点开始，顺序遍历得到该节点的前序节点，并完成删除操作。

最后需要注意的是，如果链表中只有一个节点，而我们又要删除链表的头节点（也是尾节点），那么，此时我们在删除节点之后，还需要把链表的头节点设置为nullptr

问题

题目一：在 0(1)时间内删除链表节点。 给定单向链表的头指针和一个节点指针，定义一个函数在0(1)时间内删除该节点。

代码

方法1

/**
 * 给定单向链表的头指针和一个结点指针，定义一个函数在0(1)时间删除该结点,
 * 【注意1：这个方法和文本上的不一样，书上的没有返回值，这个因为JAVA引用传递的原因，
 * 如果删除的结点是头结点，如果不采用返回值的方式，那么头结点永远删除不了】
 * 【注意2：输入的待删除结点必须是待链表中的结点，否则会引起错误，这个条件由用户进行保证】
 *
 * @param head        链表表的头
 * @param toBeDeleted 待删除的结点
 * @return 删除后的头结点
 */
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");
}

方法2

public void deleteNode(ListNode head,ListNode deListNode){
		if(deListNode == null || head == null){
			return ;
		}
		if(head == deListNode){
			head =null;
		}
		else{
			if(deListNode.next == null){
				ListNode pinitListNode = head;
				while(pinitListNode.next.next != null){
					pinitListNode = pinitListNode.next;
				}
				pinitListNode.next = null;
			}else{
				deListNode.data = deListNode.next.data;
				deListNode.next = deListNode.next.next;
			}
		}
	}

LeetCode

 删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。

 

现有一个链表 -- head = [4,5,1,9]，它可以表示为:

 

示例 1:

输入: head = [4,5,1,9], node = 5

输出: [4,1,9]

解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为

4 -> 1 -> 9.

 

示例 2:

输入: head = [4,5,1,9], node = 1

输出: [4,5,9]

解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为

 4 -> 5 -> 9.

 

public void deleteNode(ListNode node) {

    node.val = node.next.val;

    node.next = node.next.next;

}