CODEWITHSUNDEEP
algorithmlinked-list
user2387900
user2387900

Reputation: 215

Finding Middle element of the Linked List

I went through a problem in Linked List from a book, but I am unable to understand what it is trying to say?

Is it: 1. finding middle element but looking from starting. What do these lines mean: 

n is c????

LinkedListNode next = n.next;   // next= d;
6 n.data = next.data;  // n.data=d;
7 n.next = next.next; // c.next= e ???

I'm unable to get it, can you please have a look and tell me?

Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node.

Example:
Input: the node ‘c’ from the linked list a->b->c->d->e
Result: nothing is returned, but the new linked list looks like a->b->d->e

Solution:
Simply copy the data from the next node into this node and then delete the next node.
NOTE: This problem can not be solved if the node to be deleted is the last node in the linked list. That's ok — your interviewer wants to see you point that out. You could consider marking it as dummy in that case. This is an issue you should discuss with your interviewer.

1 public static boolean deleteNode(LinkedListNode n) {
2   if (n == null || n.next == null) {
3     return false; // Failure
4   }
5   LinkedListNode next = n.next;
6   n.data = next.data;
7   n.next = next.next;
8   return true;
9 }

Here, what could be n? Can you explain line 5,6,7? Also, why doesn't it work if n is the last element?

I am new to linked-lists. I am reading all examples of it, but was really stuck on this one.

Upvotes: 1

Views: 1142

Answers (2)

Joel
Joel

Reputation: 4772

The problem requires you to delete a node from the middle of a linked list given only a reference to the node to be deleted.

Here, what could be n?

n could be a reference to any "middle" node in the linked list, i.e., not the first or last node.

Can you explain line 5,6,7?

The problem is, since the list is not doubly-linked, you cannot delete the node given to you without breaking the linked list ( the previous node will be pointing at null ).

e.g. if we were to delete c, where would b point?

a->b->c->d->e

a->b->     d->e

Since we don't know what node came before c, we have no way of linking the list again. So the solution is to copy the values from d into node c, and then delete node d. Then the list is not broken, and you have deleted a node from it. Then the old node c will actually represent the d node, which will continue the linked list at node e.

a->b->c->d->e

a->b->d->e

Those lines are simply copying the data from node d and storing it in node c, so that node d can then be deleted.

why doesn't it work if n is the last element?

If n is the last element, the next node in the list is null, so we have nothing we can copy into the current node.

Upvotes: 2

zw324
zw324

Reputation: 27210

The lines you pointed out are doing the following:

n.data = next.data;

copies the data from the next node;

n.next = next.next;

change the next link of the "now" node; now the current node is a identical copy of the "next" node, and the next node cannot be reached from the head of the list.

In other words, this algorithm does not actually delete the current node - it copies the data from the next node to the current node and remove the next node from the linked chain, thus the data on the current node is lost, and the current node serves as the next node, the next node is effectively deleted.

If the current node is that last node, then next.data would throw a NullPointerException.

Upvotes: 1

Related Questions