Delete alternate nodes of a Linked List

You are 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->4->8->10->15 then your function should convert it to 1->8->15

Solution:

Steps:

  1. Take two pointers p and q
  2. Initially p points to head and q points to link of p i.e 2nd node .
  3. Make the link of p to point to link of q and free q.
  4. move p to its link i.e next node
  5. move q to next node of p
  6. loop until p or q becomes NULL.

 



struct node *deleteAlternative(struct node *head)
{
    if(head==NULL)
        return NULL;
    struct node *p=head;
    struct node *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;

Complexity: O(n)

6 Thoughts on “Delete alternate nodes of a Linked List

  1. michael kors purses on September 23, 2014 at 4:34 pm said:

    Excellent blog here! not really your web site lots out and about fast. . . Wushanka web host which you’ll find you use? this may I plot a route your associate link to your pitch? then i wish these site loaded up as fast ap oker yours hehe

  2. Alternative.. Please suggest if any improvement is required.

    void DeleteAlternative(struct ListNode *head)
    {
    struct ListNode *current;
    struct ListNode *Connect=new struct ListNode;
    struct ListNode *temp;
    current=head;

    while(current!=NULL)
    {
    temp=current->next;
    if(temp!=NULL)
    {
    Connect=temp->next;
    current->next=Connect;
    free(temp);
    current=current->next;
    }
    else
    {
    return;
    }

    }
    }

  3. Ajay Tiwary on May 9, 2015 at 3:15 pm said:

    recursive method :-

    public static void deleteAlternate(Node head) {
    Node p = head;
    Node q = head;
    if(p==null || p.getNext()==null)
    {
    return ;
    }
    p.setNext(q.getNext().getNext());
    q=null;
    deleteAlternate(p.getNext());

    }

  4. Ajay Tiwary on May 9, 2015 at 3:24 pm said:

    modified recursive method:-Objects are being derefrenced properly in this version of code.Please ignore my first reply

    public static void deleteAlternate(Node head) {
    Node p = head;
    Node q = head;
    if(p==null || p.getNext()==null)
    {
    return ;
    }
    q = q.getNext();
    p.setNext(q.getNext());
    q=null;
    deleteAlternate(p.getNext());

    }

  5. private static void deleteAlternate(Node head) {
    Node ptr = head;

    while(ptr!=null)
    {
    Node temp =ptr.getNext();
    ptr.setNext(temp.getNext());
    temp = null;
    ptr = ptr.getNext();

    }

    }

  6. Ajay Tiwary on April 7, 2016 at 11:26 am said:

    private static void deleteAlternate(Node head) {

    if(head==null)
    {
    return;
    }
    Node temp = head;
    Node newTemp = temp.getNext();
    Node k =newTemp.getNext();
    temp.setNext(k);
    newTemp = null;
    deleteAlternate(k);

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation