面試題13.在O(1)時間删除連結清單節點

題目描述：

給定單連結清單的頭指針和一個結點指針，實作在O(1)的時間複雜度内，删除該結點。結點的定義為：

class Node
    Node next;
    int val;

    Node(int val) {
        this.val = val;
    }
}      

思路：

假設目前的連結清單是：0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6，我們要删除4這個結點

通常的想法是，掃描整個連結清單，當遇到要删除的結點後，删除之。比如，我們掃描到3，發現下一個就是要删除的結點4，然後我們修改3的next指針，使之指向5，然後把4的next指針指向null，這樣就把4從這個連結清單中删除了。很顯然，這種方法的時間複雜度是O(n)。

為了得到時間複雜度為O(1)的方法，我們采用複制值的方法，把待删除節點的下一個結點的值，複制給待删除結點，然後删除下一個結點即可。具體說來：

• 把結點5的值複制給結點4，然後删除結點5，直接一步到位删除結點。

這個思路的代碼如下：

/**
 * O(1)時間内删除連結清單的結點
 * @author

class Node {
    Node next;
    int val;

    Node(int val) {
        this.val = val;
    }
}

public class Main

    public static void delete(Node head, Node node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }

    public static void main(String[] args) {
        // test case
        int[] arr = new int[]{0,1,2,3,4,5,6};

        Node[] list = new Node[arr.length];
        for(int i = 0; i < arr.length; i++) {
            list[i] = new Node(i);
        }

        for(int i = 0; i < list.length-1; i++) {
            Node node = list[i];
            Node next_node = list[i+1];
            node.next = next_node;
        }

        Node head = list[0];
        delete(head, list[4]);

        while(head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }
}