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