CODEWITHSUNDEEP
c++
nikhil
nikhil

Reputation: 9385

Altering a linked list

You are given a Single Linked List a->b->c->d->1->2->3->4->e->f->g->h->5->6->7->8 . You have to alter this list to look like a->1->b->2->c->3->d->4->e->5->f->6->g->7->h->8 .

My approach uses an extra list where we remove the numbers form the list and store them separately. Then to merge the lists together. Can someone suggest better techniques to do this?

Upvotes: 3

Views: 362

Answers (2)

GG.
GG.

Reputation: 2951

Take 2 pointers and increment 2nd pointers until you get a number and as soon as you get a number remove the node from here and insert after first pointer.

Since its an interview question, interviewer might be looking at how are you handling all the corner cases like list is null, only two nodes(1-char & 1-int), number of character node and integer node are different in number in a block etc.

Upvotes: 1

josh shadowfax
josh shadowfax

Reputation: 304

I would have two iterators. Have one (iterator A) run through the list, stopping when you hit a number, and have the other (iterator B) stay at the start of the list. When you hit a number, insert the node at iterator A after the node at iterator B, then move iterator B up. In this way you don't have to make a separate list.

EDIT: Remove the item at iterator A after you insert it at B (thanks to Tudor for catching).

Upvotes: 8

Related Questions