Let x be a node in SLL. Write a C++ function to delete the data in this node. Following this deletion, the number of nodes in the list is one less than before the deletion. Your function must run for O(1).

Actually its a project for me that i would like to know the answer. would be pleased if u show me the solution. pls

But you won't learn anything by being given the answer. The trick is to think outside the box a little bit. Naively deleting a node from a single linked list is O(n) because you have to find the previous node for unlinking. So what can you do to avoid needing the previous node?

Make the next node at first??

I'm having trouble deciphering what you mean, but it sounds like you're thinking in the right direction.

Here's a hint: the problem doesn't state that you only have to do this by diddling with the links between nodes.

Did you figure it out? As mentioned before, I really am trying to help, but without flat out giving you the answer.

Consider this: Swap the data with the next node, then delete the next node. This is what I mean by thinking outside the box.

Thinking through these types of problems on a simple data structure like a linked list is invaluable for when you move on to more complex data structures. In particular, this swap and delete technique is very handy with trees. But the reason I'm directing you rather than simply gaving away answers is because if you only know the specific technique for that data structure, variations of it for other data structures don't stand out as readily.

Edited 2 Years Ago by deceptikon

You are getting help, yet still you sent (10mins ago) a PM begging me to help you as you have to submit a project tomorrow and don't have time to do it yourself...

Please don't do that again.

This article has been dead for over six months. Start a new discussion instead.