Delete every mth element in a linked list ??

Discussion in 'C++' started by Aditya, Dec 20, 2006.

  1. Aditya

    Aditya Guest

    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
     
    Aditya, Dec 20, 2006
    #1
    1. Advertising

  2. * 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?

    --
    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?
     
    Alf P. Steinbach, Dec 20, 2006
    #2
    1. Advertising

  3. On Dec 20, 10:33 am, "Aditya" <> wrote:
    > 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)
    {
    }

    --
    Erik Wikström
     
    =?iso-8859-1?q?Erik_Wikstr=F6m?=, Dec 20, 2006
    #3
  4. "Aditya" <> writes:

    > 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.
     
    Rud1ger Sch1erz, Dec 20, 2006
    #4
  5. Aditya

    Salt_Peter Guest

    Aditya wrote:
    > 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 ).

    > }
    >
    > thanks
    > A
     
    Salt_Peter, Dec 20, 2006
    #5
  6. Aditya

    Mark P Guest

    Aditya wrote:
    > 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?
     
    Mark P, Dec 20, 2006
    #6
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris Ritchey
    Replies:
    7
    Views:
    484
    emerth
    Jul 10, 2003
  2. Chris Ritchey

    Generating a char* from a linked list of linked lists

    Chris Ritchey, Jul 9, 2003, in forum: C Programming
    Replies:
    7
    Views:
    472
    emerth
    Jul 10, 2003
  3. fool
    Replies:
    14
    Views:
    512
    Barry Schwarz
    Jul 3, 2006
  4. Aditya
    Replies:
    11
    Views:
    704
    Richard Heathfield
    Dec 21, 2006
  5. joshd
    Replies:
    12
    Views:
    674
    John Carson
    Oct 2, 2006
Loading...

Share This Page