Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C++ (http://www.velocityreviews.com/forums/f39-c.html)
-   -   Delete every mth element in a linked list ?? (http://www.velocityreviews.com/forums/t459337-delete-every-mth-element-in-a-linked-list.html)

Delete every mth element in a linked list ??

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

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:

{
}

thanks
A

 Alf P. Steinbach 12-20-2006 09:56 AM

Re: Delete every mth element in a linked list ??

> 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)
> {
> }

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?

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

 =?iso-8859-1?q?Erik_Wikstr=F6m?= 12-20-2006 10:26 AM

Re: Delete every mth element in a linked list ??

> 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)
> {
>
> }

Start by rewriting that as:

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

--
Erik Wikström

 Rud1ger Sch1erz 12-20-2006 10:35 AM

Re: Delete every mth element in a linked list ??

> 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

--
The next sentence is wrong.
The previous sentence is right.

 Salt_Peter 12-20-2006 04:37 PM

Re: Delete every mth element in a linked list ??

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

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

> }
>
> thanks
> A

 Mark P 12-20-2006 10:11 PM

Re: Delete every mth element in a linked list ??

> 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)
> {
> }
>
> 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