Remove an item from a singly linked list. Next: do it with no additional memory usage

Question

Anónimo · Accepted Answer

Well, I think it's possible to do it in clean way.
Assume the linked list is like this and you have to remove 3:
1->2->3->4->5
You start iterating from the 1st node and when you reach node 3, you just say node.val = node.next.val and node.next = node.next.next.
So essentially you are replacing 3rd element with 4th and removing the 4th element.
Does this make sense?

Anónimo · Answer

You int need to replace any element. In case of your example, just iterate till (node.next.value == delete_element_val). Then just do (node.next = node.next.next). In this method, you have to take care of special case where the element to be deleted is last element. So : No extra memory, no replacement and Complexity is O(n) with auxiliary O(1).

Anónimo · Answer

First one was easy, just store curNode and relink everything properly. When restraints started being added on, it got a little ridiculous. In the end, they told me I should have moved the data in the nodes over until the last one was the one to delete.

I think this is totally wrong. First of all singly linked lists are hardly ever a more efficient data structure to use. Second, shuffling data between nodes defeats the purpose of having the nodes. They are supposed to be self-contained structures holding related data, and moving them around kills that whole notion.

Intuit

Pregunta de entrevista de Intuit

Respuestas de entrevistas

Empresas seguidas

Búsquedas de empleo