LeetCode Delete Node in a Linked ListQuestion题目分析代码

Question

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

题目

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

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

分析

一般，删除链表节点需要前置节点，需要n的时间复杂度。但这里要实现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
        node.val = node.next.val;
        node.next = node.next.next;
    }
}