Delete a last node of linked list given pointer to that node

Question

I'm trying to delete the last node of the linkedlist, given pointer only to that node.

I wrote the below implementation, but isn't working.

I already visited majority of SO questions regarding this subject, but none of them shows how to delete last node of linked list, if there's only one pointer to that node ?

Am I missing anything here ?

class Node {

        Node next;
        int value;

        Node(int val) {
                this.value = val;
                this.next = null;
        }

        @Override
        public String toString() {
                Node cur = this;
                String str = "";

                while(cur != null) {
                        str += cur.value+"->";
                        cur = cur.next;
                }

                return str;
        }
}

class DeleteNodeLL {

    public static void deleteNode(Node current) {
        Node temp;
        if(current.next == null) {
            current = null;
            return;
        } else {
            current.value = current.next.value;
            temp = current.next;
            temp = null;
            current.next = current.next.next;
        }

    }
    public static void main(String [] args) {

        Node n1 = new Node(25);
        Node n2 = new Node(1);
        Node n3 = new Node(36);
        Node n4 = new Node(9);
        Node n5 = new Node(14);

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = null;

        System.out.println("Original linkedlist :");
        System.out.println(n1);

        System.out.println();

        System.out.println("After deleting a node :");
        deleteNode(n5);
        System.out.println(n1);
    }
}

Output :-

Original linkedlist :
25->1->36->9->14->

After deleting a node :
25->1->36->9->14->

^ I don't have any pointer, except for pointer to last node. So your solution won't work — tmgr
– tmgr, Commented Jul 9, 2013 at 3:22
There is no solution that will work for single-linked list. Please recheck your assignment... — Alexei Levenkov
– Alexei Levenkov, Commented Jul 9, 2013 at 3:23
Then I don't think it would be possible because you previous node's next still has that deleted location — banarun
– banarun, Commented Jul 9, 2013 at 3:24
Without a pointer to the previous node as well, it's not possible to delete the last node.I think your prof want's you to make this observation.If you have access to the head pointer, then the given task is possible.Do you have access to head pointer? — Aravind
– Aravind, Commented Jul 9, 2013 at 7:33

asifsid88 · Accepted Answer · 2013-07-09 04:45:37Z

5

With the singly linked list it is not possible.
This is the interview questions which is typically asked in Big Shot companies which emphasizes on Data Structures.
The question is formulated as "Delete the node in single linked list given pointer to only that node"
Expected Solution:

public void deleteNode(Node n)
{
    if(n==null || n.next==null)
    {
        System.out.println("Delete not possible");
        return;
    }

    n.data = n.next.data;
    Node tmp = n.next;
    n.next = n.next.next;
    tmp.next = null;

    System.out.println("Node Deleted");
}

The idea is to copy the data from the next node to the current node and delete the next node. The solution does not work if the node is the last node (This is what candidate has to debate and point out in interview)

Hope it helps you! (Solution to your problem is a trick question, and it does not exists)

edited Jul 9, 2013 at 4:45

answered Jul 9, 2013 at 4:27

asifsid88

4,71122 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Alex Shesterov · Accepted Answer · 2013-07-09 03:31:15Z

3

current = null; doesn't do what you expect - it only sets local variable (method argument) to null.

What you want is impossible with your current implementation of the Node class. You need either a reference to the previous node inside the Node class (i.e. a doubly-linked list) or you have to provide a reference to some previous node to the deleteNode method.

edited Jul 9, 2013 at 3:31

answered Jul 9, 2013 at 3:25

Alex Shesterov

27.8k14 gold badges91 silver badges110 bronze badges

Comments

RaceBase · Accepted Answer · 2013-07-09 06:24:09Z

0

I would say

You can delete the last node from the Linked List if reference of it's previous node is given.

However it's based on how you implement the list.

For your implementation, you can't do that

answered Jul 9, 2013 at 6:24

RaceBase

19k50 gold badges151 silver badges211 bronze badges

Comments

Messiah · Accepted Answer · 2013-07-12 14:33:26Z

0

The only solution to this question is to iterate over the complete list keeping the prev node pointer everytime, compare the current node with the present node. When the comparison passes, delete the last node, and point the prev node to null. Something like the code below(note: I did not compile it)

deleteNode(Node *node){
if(node){
currentNode = Head, prevNode = NULL;
while(currentNode != node){
prevNode = currentNode;
currentNode = currentNode -> next;
}
delete currentNode;
prevNode -> next = NULL;
}
}

answered Jul 12, 2013 at 14:33

Messiah

997 bronze badges

Comments

PJ Tang · Accepted Answer · 2014-03-26 19:25:26Z

0

@asifsid88 copied and pasted the solutions from "cracking the coding", you should refer to that book to find more interesting and challenging questions.

answered Mar 26, 2014 at 19:25

PJ Tang

192 silver badges5 bronze badges

Collectives™ on Stack Overflow

Delete a last node of linked list given pointer to that node

5 Answers 5

Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related