Popular Posts

Thursday, July 14, 2011

Delete alternate nodes of a Linked List

Problem:
Given a Singly Linked List, starting from the second node delete all alternate nodes of it. For example, if the given linked list is 1->2->3->4->5 then your function should convert it to 1->3->5, and if the given linked list is 1->2->3->4 then convert it to 1->3.
Solution:
  •   Have two pointers p and q
  • Initially p points head and q points to link of p i.e 2nd node (if exists).
  • Make the link of p to point to link of q
  • free q
  • move p to its link i.e next node
  • move q to next node of p
  • loop until p or q becomes NULL.

Complexity: O(n)
Code:

List *deletealternative(List *head)
{
    if(head==NULL)
        return NULL;
    List *p=head;
    List *q=p->link;
    
    while(p!=NULL && q!=NULL)
    {
        p->link=q->link;
        free(q);
        p=p->link;
        if(p!=NULL)
            q=p->link;
    }
    return head;
}

No comments:

Post a Comment