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:
- Take two pointers p and q
- Initially p points to head and q points to link of p i.e 2nd node .
- Make the link of p to point to link of q and 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.
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)
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
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;
}
}
}
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());
}
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());
}
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();
}
}
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);