博客

一、题目描述

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


样例


给定 1->2->3->4，和节点 3，删除 3 之后，链表应该变为 1->2->4

题目链接：

删除链表结点

二、解题思路

最常规的做法是：从链表的头结点开始，顺序遍历整个链表，找到要删除的结点，然后在链表当中删除该结点。这种方法由于要顺序查找，时间复杂度自然就为O(n).这种解法之所以需要从头开始查找，是因为我们需要得到待删除结点的前一个结点pre,然后通过pre.next = pre.next.next;来删除待删除的结点。

那么如何在O(1)时间复杂度内在链表中删除指定结点呢？我们可以很容易的得到待删除结点的下一个结点。如果我们

把下一个结点的内容复制到待删除结点，然后再把下一个结点删除，就相当于把当前需要删除的结点给删除了。

三、代码实现

/**
 * 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) {
        // write your code here
        ListNode nextNode = node.next;  //待删除结点的下一个结点nextNode
        node.val = nextNode.val;    //将下一个结点的值赋给要删除的结点
        node.next = nextNode.next;  //删除下一个结点
    }
}