Question

I was practicing program problems without answer.

Not sure on how to write this program and I need help. it needs to be in C language. Thank you!

Assume the node structure is as follows: struct node { int data; struct node "next; struct node "prev; please write a function struct node *merge(struct node *g. struct node 'n) to merge two doubly linked lists contains integer numbers without duplicates in the increasing order. You have to remove duplicates. Also show how to call this function.

Answer 1

/*

Following program implemented using DEV C++

you can try with any C compiler also

*/

#include<stdio.h>
//declaration of Node
struct Node {
//consist data data and next and prev address
    int data;
    Node *next, *prev;
};
void removeDuplicates(Node* head)
{
    Node* curNode = head;
    Node* next_next;
    if (curNode == NULL)
        return;

  
    while (curNode->next != NULL) {
        /* Compare curNode node with next node */
        if (curNode->data == curNode->next->data) {

            /* The sequence of steps is important*/
            next_next = curNode->next->next;
          
            curNode->next = next_next;
        }
        else /* This is tricky: only advance if no deletion */
        {
            curNode = curNode->next;
        }
    }
}

void AddNode(Node** addr_head, int data)
{
    //allocate memory for new born node
    Node* new_node = new Node;
// add data to it
    new_node->data = data;
//if list empty
    if (*addr_head == NULL) {
        new_node->next = new_node;
        new_node->prev = new_node;
    }
// add node at end
    else {
    
        Node* last = (*addr_head)->prev;
        new_node->next = *addr_head;
        new_node->prev = last;
        last->next = (*addr_head)->prev = new_node;
    }
    *addr_head = new_node;
}

//called merge recusrsivly till list end
Node* merge(Node* fnode, Node* snode)
{
    // first list is empty
    if (!fnode)
        return snode;

    // second list is empty
    if (!snode)
        return fnode;
//comparing data and calling merge function recurverly
    if (fnode->data < snode->data) {
        fnode->next = merge(fnode->next, snode);
        fnode->next->prev = fnode;
        fnode->prev = NULL;
        return fnode;
    }
  
//comparing data and calling merge function recurverly
    else {
        snode->next = merge(fnode, snode->next);
        snode->next->prev = snode;
        snode->prev = NULL;
        return snode;
    }
}

//mergingg list
Node* Merge(Node* FirstHead, Node* Secondhead)
{
   //fiesr list is empty
    if (!FirstHead)
        return Secondhead;

    //second list is empty
    if (!Secondhead)
        return FirstHead;

   //going till end of list
    Node* last_node;
    if (FirstHead->prev->data < Secondhead->prev->data)
        last_node = Secondhead->prev;
    
    else
        last_node = FirstHead->prev;
// adding null at end
    FirstHead->prev->next = Secondhead->prev->next = NULL;

    //merginng sorted list
    Node* newhead = merge(FirstHead, Secondhead);

    newhead->prev = last_node;
    last_node->next = NULL;
    // removing duplicate if any
    removeDuplicates(newhead);

    return newhead;
}

// method to print all node
void Display_List(Node* head)
{
    Node* nodetemp = head;

    while (nodetemp->next != NULL) {
        printf("%d ",nodetemp->data);
        nodetemp = nodetemp->next;
    }
     printf("%d ",nodetemp->data);
}

int main()
{
    Node *FirstHead = NULL, *Secondhead = NULL;

    // Linked List 1
    AddNode(&FirstHead, 2);
    AddNode(&FirstHead, 55);
    AddNode(&FirstHead, 33);
    AddNode(&FirstHead, 1);

    //Linked List 2
    AddNode(&Secondhead, 11);
    AddNode(&Secondhead, 4);
    AddNode(&Secondhead, 7);
    AddNode(&Secondhead, 2);

    Node* Head = Merge(FirstHead, Secondhead);

    printf("Final Sorted List: ");
    Display_List(Head);

    return 0;
}

/*

output

Final Sorted List: 1 2 7 4 11
--------------------------------
Process exited after 0.06974 seconds with return value 0
Press any key to continue . . .

*/

130 C:\Users\Harsh\Desktop\C++ Program\merge_doubly_linked_list.cpp - Dev-C++ 5.11 File Edit Search View Project Execute Tools AStyle Window Help 2 BB AB :: DB.: * d TDM-GCC 4.9.2 64-bit Release 0 (globals) Project Classes Debug merge_doubly_linked_list.cpp 129 // Linked List 1 AddNode(&FirstHead, 2); AddNode(&FirstHead, 55); AddNode(&FirstHead, 33); C:\Users\Harsh\Desktop\C++ Program merge_doubly_linked_list.exe AddNode(&FirstHead, 1); Final Sorted List: 1 2 7 4 11 135 //Linked List 2 Process exited after 0.06974 seconds with return value o AddNode(&Secondhead, 11); Press any key to continue ... AddNode(&Secondhead, 4); AddNode(&Secondhead, 7); AddNode(&Secondhead, 2); - - - - - - - - - - - - - - - - - - - - - - - 137 139 142 Node* Head = Merge(FirstHead, Secondhe printf("Final Sorted List: "); Display_List(Head); 145 return 0; 147 148 L} 89 Compiler Resources dlh Compile Log ✓ Debug Find Results Close Abort Compilation Compilation results... Shorten compiler paths - Errors: 0 - Warnings: 0 - Output Filename: C:\Users\Harsh\Desktop\C++Prog - Output Size: 386.9033203125 KiB