Delete every mth element in a linked list ??

A

Aditya

This is a normal interview question, which goes like this
"Given a linked list of integers, delete every mth node and return the
last remaining node."

eg: Linked list = 4->6->7->3->5->6->10->1->23->17
Delete every 3rd node (m = 3) and return the last remaining node
meaning...
4->6->3->5->10->1->17
4->3->5->1->17
3->5->17
3->17
3

after deleting every 3rd node the last remaining node is 3, so node
with data 3 is returned.
function prototype:

node* deleteEveryMth(node** head, int m)
{
// .... your code
}

thanks
A
 
A

Alf P. Steinbach

* Aditya:
This is a normal interview question, which goes like this
"Given a linked list of integers, delete every mth node and return the
last remaining node."

eg: Linked list = 4->6->7->3->5->6->10->1->23->17
Delete every 3rd node (m = 3) and return the last remaining node
meaning...
4->6->3->5->10->1->17
4->3->5->1->17
3->5->17
3->17
3

after deleting every 3rd node the last remaining node is 3, so node
with data 3 is returned.
function prototype:

node* deleteEveryMth(node** head, int m)
{
// .... your code
}

Although the article quoted above is off-topic, it's interesting that
there's seemingly no consistent system in the example, and an
underspecified and at the same time overspecified example to be filled
out. With a meaningless argument. Are you sure this was all part of
the homework problem, or is it your elaboration?
 
?

=?iso-8859-1?q?Erik_Wikstr=F6m?=

This is a normal interview question, which goes like this
"Given a linked list of integers, delete every mth node and return the
last remaining node."

eg: Linked list = 4->6->7->3->5->6->10->1->23->17
Delete every 3rd node (m = 3) and return the last remaining node
meaning...
4->6->3->5->10->1->17
4->3->5->1->17
3->5->17
3->17
3

after deleting every 3rd node the last remaining node is 3, so node
with data 3 is returned.
function prototype:

node* deleteEveryMth(node** head, int m)
{
// .... your code

}

Start by rewriting that as:

template<class T>
T& deleteEveryMth(std::list<T>, unsigned int m)
{
}
 
R

Rud1ger Sch1erz

Aditya said:
after deleting every 3rd node the last remaining node is 3, so node
with data 3 is returned.

Well, could be solved with some kind of recursive function call.

Cheers,
Rudiger
 
S

Salt_Peter

Aditya said:
This is a normal interview question, which goes like this
"Given a linked list of integers, delete every mth node and return the
last remaining node."

eg: Linked list = 4->6->7->3->5->6->10->1->23->17
Delete every 3rd node (m = 3) and return the last remaining node
meaning...
4->6->3->5->10->1->17
4->3->5->1->17
3->5->17
3->17
3

after deleting every 3rd node the last remaining node is 3, so node
with data 3 is returned.
function prototype:

node* deleteEveryMth(node** head, int m)
{
// .... your code

Looks like C, not C++.
A list of nodes should never expose its nodes. deleteEveryMth(...)
needs to be templated and takes a reference to a List, returns the
template parameter ( see Erik's Post ).
 
M

Mark P

Aditya said:
This is a normal interview question, which goes like this
"Given a linked list of integers, delete every mth node and return the
last remaining node."

eg: Linked list = 4->6->7->3->5->6->10->1->23->17
Delete every 3rd node (m = 3) and return the last remaining node
meaning...
4->6->3->5->10->1->17
4->3->5->1->17
3->5->17
3->17
3

after deleting every 3rd node the last remaining node is 3, so node
with data 3 is returned.
function prototype:

node* deleteEveryMth(node** head, int m)
{
// .... your code
}

thanks
A

Your description makes no sense as written (how do you know there's only
one remaining node?) nor does it agree with your example ('6' is the
second node in the list so how does it get deleted in step two?). I
think what you meant to ask, reading between the lines of your example,
is how to delete every mth node from a _circularly_ linked list until
only one node remains.

Why don't you give it a try and show us what you come up with?
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,899
Latest member
RodneyMcAu

Latest Threads

Top