Ideone.com

fork download

copy

#include <iostream>
using namespace std;
 
struct node
{
    int data;
    struct node *next;
};
 
//struct node* head = NULL;
 
 
//Normally node* head fetches the address of the head from &head and **head stores the address of (address of head)
//But here head(whose refrence is passed) itself is a pointer defined using struct
//So in order to store address of a pointer we need double pointer
void insert_first(struct node** head,int data)
{
    struct node* temp = new node();
    temp->data = data;
    //so for acessing the value of head pointer we need to de-reference it first uding *head
    temp->next = *head;
    *head = temp;
}
 
void insert_last(struct node** head,int data)
{
    struct node* temp = new node();
    temp->data = data;
    temp->next = NULL;
 
    struct node* p = *head;
    if(p==NULL)
    {insert_first(head,data);}
    else
    {
        while(p->next!=NULL)
        {p = p->next;}
 
        p->next = temp;
    }
}
 
 
 
void deleted(struct node** head,int key)
{
    struct node *curr,*prev;
    curr=*head;
 
    if(curr->data==key)
    {
        *head = curr->next;
        delete(curr);
    }
    else
    {
        while(curr->next->data!=key)
            curr = curr->next;
 
        prev = curr->next;              //used just for deleteing the free space else one pointyer is sufficient    
        curr->next = curr->next->next;
        delete(prev);
    }
}
 
void insert_mid(struct node** head,int key,int data)
{
    struct node* temp = new node();
    temp->data=data;
    temp->next=NULL;
 
    struct node* p = *head;
    while(p->data!=key)
        p = p->next;
 
    temp->next = p->next;
    p->next = temp;
}
 
void reverse(struct node** head)
{
    struct node *c,*p,*temp;
    c= *head;
    p=NULL;
 
    while(c->next!=NULL)
    {
        temp = c;
        c = c->next;
        temp->next=p;
        p = temp;
    }
    c->next = p;
    *head = c;
}
 
 
void print_list(struct node** head)
{
    struct node* p = *head;
    while(p!=NULL)
    {
        cout<<p->data<<endl;
        p=p->next;
    }
}
 
node* SortedMerge(node* head1,   node* head2)
{
    struct node* temp = new node();
    struct node *p1 = head1,*temp1 = head1;
    struct node* p2 = head2,*temp2 = head2;
    while(p1 && p2)
    {
           if(head1->data > head2->data)
        {
            temp->data = head2->data;
            temp->next = head1;
            head1 = temp;
 
            p2 = head2->next;
            p1 = head1->next;
        }
 
        if(p1->data < p2->data)
        {
            p1 = p1->next;
            temp1 = temp1->next;
        }
        else
        {
            temp->data = p2->data;
            temp->next = p1;
            temp1->next = temp;
 
            p2 = p2->next;
            temp1 = temp1->next;
            temp2 = temp2->next;
        }
    }
    if(p1==NULL && p2!=NULL)
        {
            temp1->next = p2;
        }
        //If p2 is NULL mean all its eleemnt are added in the list
    return head1;
 
}
 
int main()
{
    struct node* head = NULL;
    struct node* head1 = NULL;
 
    //&head is used to pass the address of thye head pointer
    insert_last(&head,20);
    insert_first(&head,10);
    insert_first(&head,1);
    insert_last(&head,30);
 
    //print_list(&head);
    cout<<endl;
    insert_last(&head,40);
    insert_mid(&head,20,25);
    insert_mid(&head,1,5);
 
    deleted(&head,5);
    deleted(&head,1);
    //reverse(&head);
 
    insert_first(&head1,11);
    insert_first(&head1,2);
 
    struct node* res = SortedMerge(head,head1);
    print_list(&res);
 
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKc3RydWN0IG5vZGUKewogICAgaW50IGRhdGE7CiAgICBzdHJ1Y3Qgbm9kZSAqbmV4dDsKfTsKCi8vc3RydWN0IG5vZGUqIGhlYWQgPSBOVUxMOwoKCi8vTm9ybWFsbHkgbm9kZSogaGVhZCBmZXRjaGVzIHRoZSBhZGRyZXNzIG9mIHRoZSBoZWFkIGZyb20gJmhlYWQgYW5kICoqaGVhZCBzdG9yZXMgdGhlIGFkZHJlc3Mgb2YgKGFkZHJlc3Mgb2YgaGVhZCkKLy9CdXQgaGVyZSBoZWFkKHdob3NlIHJlZnJlbmNlIGlzIHBhc3NlZCkgaXRzZWxmIGlzIGEgcG9pbnRlciBkZWZpbmVkIHVzaW5nIHN0cnVjdAovL1NvIGluIG9yZGVyIHRvIHN0b3JlIGFkZHJlc3Mgb2YgYSBwb2ludGVyIHdlIG5lZWQgZG91YmxlIHBvaW50ZXIKdm9pZCBpbnNlcnRfZmlyc3Qoc3RydWN0IG5vZGUqKiBoZWFkLGludCBkYXRhKQp7CiAgICBzdHJ1Y3Qgbm9kZSogdGVtcCA9IG5ldyBub2RlKCk7CiAgICB0ZW1wLT5kYXRhID0gZGF0YTsKICAgIC8vc28gZm9yIGFjZXNzaW5nIHRoZSB2YWx1ZSBvZiBoZWFkIHBvaW50ZXIgd2UgbmVlZCB0byBkZS1yZWZlcmVuY2UgaXQgZmlyc3QgdWRpbmcgKmhlYWQKICAgIHRlbXAtPm5leHQgPSAqaGVhZDsKICAgICpoZWFkID0gdGVtcDsKfQoKdm9pZCBpbnNlcnRfbGFzdChzdHJ1Y3Qgbm9kZSoqIGhlYWQsaW50IGRhdGEpCnsKICAgIHN0cnVjdCBub2RlKiB0ZW1wID0gbmV3IG5vZGUoKTsKICAgIHRlbXAtPmRhdGEgPSBkYXRhOwogICAgdGVtcC0+bmV4dCA9IE5VTEw7CiAgICAKICAgIHN0cnVjdCBub2RlKiBwID0gKmhlYWQ7CiAgICBpZihwPT1OVUxMKQogICAge2luc2VydF9maXJzdChoZWFkLGRhdGEpO30KICAgIGVsc2UKICAgIHsKICAgICAgICB3aGlsZShwLT5uZXh0IT1OVUxMKQogICAgICAgIHtwID0gcC0+bmV4dDt9CiAgICAgICAgCiAgICAgICAgcC0+bmV4dCA9IHRlbXA7CiAgICB9Cn0KCgoKdm9pZCBkZWxldGVkKHN0cnVjdCBub2RlKiogaGVhZCxpbnQga2V5KQp7CiAgICBzdHJ1Y3Qgbm9kZSAqY3VyciwqcHJldjsKICAgIGN1cnI9KmhlYWQ7CiAgICAKICAgIGlmKGN1cnItPmRhdGE9PWtleSkKICAgIHsKICAgICAgICAqaGVhZCA9IGN1cnItPm5leHQ7CiAgICAgICAgZGVsZXRlKGN1cnIpOwogICAgfQogICAgZWxzZQogICAgewogICAgICAgIHdoaWxlKGN1cnItPm5leHQtPmRhdGEhPWtleSkKICAgICAgICAgICAgY3VyciA9IGN1cnItPm5leHQ7CiAgICAgICAgCiAgICAgICAgcHJldiA9IGN1cnItPm5leHQ7ICAgICAgICAgICAgICAvL3VzZWQganVzdCBmb3IgZGVsZXRlaW5nIHRoZSBmcmVlIHNwYWNlIGVsc2Ugb25lIHBvaW50eWVyIGlzIHN1ZmZpY2llbnQgICAgCiAgICAgICAgY3Vyci0+bmV4dCA9IGN1cnItPm5leHQtPm5leHQ7CiAgICAgICAgZGVsZXRlKHByZXYpOwogICAgfQp9Cgp2b2lkIGluc2VydF9taWQoc3RydWN0IG5vZGUqKiBoZWFkLGludCBrZXksaW50IGRhdGEpCnsKICAgIHN0cnVjdCBub2RlKiB0ZW1wID0gbmV3IG5vZGUoKTsKICAgIHRlbXAtPmRhdGE9ZGF0YTsKICAgIHRlbXAtPm5leHQ9TlVMTDsKICAgIAogICAgc3RydWN0IG5vZGUqIHAgPSAqaGVhZDsKICAgIHdoaWxlKHAtPmRhdGEhPWtleSkKICAgICAgICBwID0gcC0+bmV4dDsKICAgICAgICAKICAgIHRlbXAtPm5leHQgPSBwLT5uZXh0OwogICAgcC0+bmV4dCA9IHRlbXA7Cn0KCnZvaWQgcmV2ZXJzZShzdHJ1Y3Qgbm9kZSoqIGhlYWQpCnsKICAgIHN0cnVjdCBub2RlICpjLCpwLCp0ZW1wOwogICAgYz0gKmhlYWQ7CiAgICBwPU5VTEw7CiAgICAKICAgIHdoaWxlKGMtPm5leHQhPU5VTEwpCiAgICB7CiAgICAgICAgdGVtcCA9IGM7CiAgICAgICAgYyA9IGMtPm5leHQ7CiAgICAgICAgdGVtcC0+bmV4dD1wOwogICAgICAgIHAgPSB0ZW1wOwogICAgfQogICAgYy0+bmV4dCA9IHA7CiAgICAqaGVhZCA9IGM7Cn0KCgp2b2lkIHByaW50X2xpc3Qoc3RydWN0IG5vZGUqKiBoZWFkKQp7CiAgICBzdHJ1Y3Qgbm9kZSogcCA9ICpoZWFkOwogICAgd2hpbGUocCE9TlVMTCkKICAgIHsKICAgICAgICBjb3V0PDxwLT5kYXRhPDxlbmRsOwogICAgICAgIHA9cC0+bmV4dDsKICAgIH0KfQoKbm9kZSogU29ydGVkTWVyZ2Uobm9kZSogaGVhZDEsICAgbm9kZSogaGVhZDIpCnsKICAgIHN0cnVjdCBub2RlKiB0ZW1wID0gbmV3IG5vZGUoKTsKICAgIHN0cnVjdCBub2RlICpwMSA9IGhlYWQxLCp0ZW1wMSA9IGhlYWQxOwogICAgc3RydWN0IG5vZGUqIHAyID0gaGVhZDIsKnRlbXAyID0gaGVhZDI7CiAgICB3aGlsZShwMSAmJiBwMikKICAgIHsKICAgICAgICAgICBpZihoZWFkMS0+ZGF0YSA+IGhlYWQyLT5kYXRhKQogICAgICAgIHsKICAgICAgICAgICAgdGVtcC0+ZGF0YSA9IGhlYWQyLT5kYXRhOwogICAgICAgICAgICB0ZW1wLT5uZXh0ID0gaGVhZDE7CiAgICAgICAgICAgIGhlYWQxID0gdGVtcDsKICAgICAgICAgICAgCiAgICAgICAgICAgIHAyID0gaGVhZDItPm5leHQ7CiAgICAgICAgICAgIHAxID0gaGVhZDEtPm5leHQ7CiAgICAgICAgfQoKICAgICAgICBpZihwMS0+ZGF0YSA8IHAyLT5kYXRhKQogICAgICAgIHsKICAgICAgICAgICAgcDEgPSBwMS0+bmV4dDsKICAgICAgICAgICAgdGVtcDEgPSB0ZW1wMS0+bmV4dDsKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgdGVtcC0+ZGF0YSA9IHAyLT5kYXRhOwogICAgICAgICAgICB0ZW1wLT5uZXh0ID0gcDE7CiAgICAgICAgICAgIHRlbXAxLT5uZXh0ID0gdGVtcDsKICAgICAgICAgICAgCiAgICAgICAgICAgIHAyID0gcDItPm5leHQ7CiAgICAgICAgICAgIHRlbXAxID0gdGVtcDEtPm5leHQ7CiAgICAgICAgICAgIHRlbXAyID0gdGVtcDItPm5leHQ7CiAgICAgICAgfQogICAgfQogICAgaWYocDE9PU5VTEwgJiYgcDIhPU5VTEwpCiAgICAgICAgewogICAgICAgICAgICB0ZW1wMS0+bmV4dCA9IHAyOwogICAgICAgIH0KICAgICAgICAvL0lmIHAyIGlzIE5VTEwgbWVhbiBhbGwgaXRzIGVsZWVtbnQgYXJlIGFkZGVkIGluIHRoZSBsaXN0CiAgICByZXR1cm4gaGVhZDE7CiAgICAKfQoKaW50IG1haW4oKQp7CiAgICBzdHJ1Y3Qgbm9kZSogaGVhZCA9IE5VTEw7CiAgICBzdHJ1Y3Qgbm9kZSogaGVhZDEgPSBOVUxMOwogICAgCiAgICAvLyZoZWFkIGlzIHVzZWQgdG8gcGFzcyB0aGUgYWRkcmVzcyBvZiB0aHllIGhlYWQgcG9pbnRlcgogICAgaW5zZXJ0X2xhc3QoJmhlYWQsMjApOwogICAgaW5zZXJ0X2ZpcnN0KCZoZWFkLDEwKTsKICAgIGluc2VydF9maXJzdCgmaGVhZCwxKTsKICAgIGluc2VydF9sYXN0KCZoZWFkLDMwKTsKICAgIAogICAgLy9wcmludF9saXN0KCZoZWFkKTsKICAgIGNvdXQ8PGVuZGw7CiAgICBpbnNlcnRfbGFzdCgmaGVhZCw0MCk7CiAgICBpbnNlcnRfbWlkKCZoZWFkLDIwLDI1KTsKICAgIGluc2VydF9taWQoJmhlYWQsMSw1KTsKICAgCiAgICBkZWxldGVkKCZoZWFkLDUpOwogICAgZGVsZXRlZCgmaGVhZCwxKTsKICAgIC8vcmV2ZXJzZSgmaGVhZCk7CiAgICAKICAgIGluc2VydF9maXJzdCgmaGVhZDEsMTEpOwogICAgaW5zZXJ0X2ZpcnN0KCZoZWFkMSwyKTsKICAgIAogICAgc3RydWN0IG5vZGUqIHJlcyA9IFNvcnRlZE1lcmdlKGhlYWQsaGVhZDEpOwogICAgcHJpbnRfbGlzdCgmcmVzKTsKCiAgICByZXR1cm4gMDsKfQ==

Runtime error #stdin #stdout 0.03s 2872KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/dgZ0eP

language:

C++ 4.3.2 (gcc-4.3.2)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language