372. 在O(1)时间复杂度删除链表节点

描述

给定一个单链表中的一个等待被删除的节点(非表头或表尾)。请在在O(1)时间复杂度删除该链表节点。

样例

Linked list is 1->2->3->4, and given node 3, delete the node in place 1->2->4

思路

对于单链表来说，一般的思路是遍历链表找到欲删除结点，然后让该结点的前结点指向该结点的后结点，实际上遍历的主要目的就是为了寻找该结点的前结点，但实际上我们不需要寻找前结点，只需要让当前结点值等于其下一结点，删除下一结点，然后当前结点指向下一结点的下一结点即可
但需要注意两种特殊情况：

1. 如果要删除结点在链表结尾，则只能用 O(n) 的遍历解法来做
2. 如果链表只有一个结点，则删除后需要把头结点设置为 NULL

代码

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param node: the node in the list should be deleted
     * @return: nothing
     */
    public void deleteNode(ListNode node) {
        if (node == null || node.next == null) {
            return;
        }
        ListNode next = node.next;
        node.val = next.val;
        node.next = next.next;
        return;
    }
}