linked list problem

Question

Delete every 't'th (t>1) node of a single linked list. In the resultant linked list, again delete 't'th node. Repeat this till only t-1 nodes remains.

For this i have come up with: Traverse until you reach 't'th node, delete all the nodes till the end. Is there any efficient way other than this?. Can any one please help me out. Thanks.

Answer 1

That sounds correct, the algorithm would be O(n).

Make sure you are deleting the t'th node though too because you only want t-1 nodes to remain.

It sounds like they want you to delete 1 node at a time always the t'th one until no more t'th nodes exist. They probably want you to do them 1 at a time so you can call delete for C++ or free for C on the node you're removing.

Answer 2

This wording of the question is rather bizarre because what is the point of repeatedly deleting t'th elements when at the end you're just left with t-1 nodes? Is this a homework question? Are you sure you've understood it correctly? If the question is indeed correct and all you care about is the end result, then doing what you've said -- deleting all nodes from t to the end, is indeed the most efficient way. The only thing to consider is that the question specifies a certain order of deleting items, and you are disregarding that order.

Answer 3

Most likely this is meant to be a circular repetitive delete. So unless the number of nodes mod t is 0, you probably need to "traverse" them one by one.

t = 4

a->b->c->d->e->f->g->h->i->j->k->l->m

here d,h,l go in the first iteration

c, i in the second and so on so forth.

Of course instead of actually traversing you can compute the node numbers that'll survive in a separate array and then delete the killees with one actual traversal.

Answer 4

Delete all nodes after t-1.

The proof is probably the true homework.

Answer 5

If you have to delete every 't'th node, you have to go through your list until you find the 't'th element and after that do the following:

while (actual.next != NULL)
{
    auxiliar = actual.next;
    actual.next = actual.next.next;
    free(auxiliar);
}

In the code above auxiliar is of node type, actual is the '(t-1)'th element, but I think this doesn't really differ from your code.

The previous comment about pointing the '(t-1)'th node to NULL wouldn't solve the problem, because we want to delete those nodes, not just to lose their address and Pieter is right about the fact that this causes memory leak (which will be your enemy for a long time).

Answer 6

/* ASSUMPTION declarations */
struct lnk_struct { int payload; struct lnk_struct * pnext; }; 
typedef struct lnk_struct LINK;

/* ASSUMPTION function prototypes */
LINK * some_func_returns_list(void); /* gives us the initial list */

int gimme_t(void);                   /* gives us value of t */

void discard_link( LINK * p );       /* frees/deletes a link */

/* IMPLEMENTATION wrapped in a procedure*/
void assignment(void)
  {
    int t = gimme_t();
    LINK * list = some_func_returns_list();
    LINK * current, * tail;
    current = list;
    /* advance current until it is t-1 'th element */
    for( /*homework you code it */)  
        {
        current = current->pnext;  
        }
    tail = current->pnext;  
    current->pnext = NULL; 
    /* now list ends where you want */
    /* you still need to delete the tail items */
    while( /* homework */ )
        {
        /* remove one link from list/
        discard_link( /* the removed link */ );
        }
  }