Monday, September 29, 2014

CC150 2.3 - Delete node in a singly linked list with only access to that node

For this interview question, the answer is not a common way to remove a node in  a singly linked list. Basically, you redirect the next node pointer of the previous node to the next pointer of the node you want to remove. Since you only have access to the current node, the tricky solution is you can replace current node with the next one. However, it is impossible to do that if the node is the last one of the list.
class Test2_3 {
    public static void main(String argv[]) {
        int todel = 4;
        if(argv.length > 0) {
            todel = Integer.parseInt(argv[0]);
        }
        Random rand = new Random(System.currentTimeMillis());
        // Create a list instance
        List list = new List();
        Node nodedel = null;
        for(int i = 0; i < 10; i++) {
            Node n = new Node(rand.nextInt(10));
            if(i == todel-1)  nodedel = n;
            list.attach(n);
        }
        System.out.printf("Remove %dth node of the list: ", todel);
        list.print();
        // Remove
        if(nodedel != null && nodedel.next != null) {
            Node next = nodedel.next;
            nodedel.data = next.data;
            nodedel.next = next.next;
        } else {
            System.out.println("Could not remove the last one!");
        }
        list.print();

    }
}   

No comments:

Post a Comment