Member Avatar for Bharath_4

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).

  • 3 Contributors
  • 11 Replies
  • 271 Views
  • 5 Hours Discussion Span
  • Latest Post Latest Post by happygeek

Recommended Answers

All 11 Replies

Member Avatar for deceptikon

Done. Show me your solution and I'll show you mine.

Member Avatar for Bharath_4

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

Member Avatar for deceptikon

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?

Member Avatar for Bharath_4

Make the next node at first?? Not sure though

Member Avatar for deceptikon

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.

Member Avatar for Bharath_4

uhh!! ok Thank You :-/

Member Avatar for deceptikon

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

Member Avatar for Bharath_4

No. I didnt find it

Member Avatar for deceptikon

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 by deceptikon
Member Avatar for Bharath_4

yeah Thanks. I could try it now .

Member Avatar for happygeek

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.