Hello All,

I am writing c++ program to insert, sort, display and merge two linked lists. Insertion, sorting and display functions are working fine but merge function is not working as expected. Please help me correcting merge function. I have used One header file "intSLLst.h" and two cpp file "intSLLst.cpp" and "main.cpp". Below are the codes:

  • intSLLst.h

    ifndef INT_LINKED_LIST
    define INT_LINKED_LIST

    class IntNode{
    public:
    int info;
    IntNode *next;
    IntNode (int el, IntNode *ptr = 0){
    info = el;
    next = ptr;
    }

    };

    class IntSLList{
    public:
    IntSLList(){
    head = tail = 0;
    }
    ~IntSLList();
    int isEmpty(){
    return head == 0;
    }
    void addToHeadLink(int);
    /void addToTail(int);
    int deleteFromHead();
    int deleteFromTail();
    void deleteNode(int);
    bool isInList(int) const;
    /
    void sort();
    void displayLink();
    void merge(IntSLList,IntSLList);

    private:
    IntNode *head, *tail;
    };

    endif
  • intSLLst.cpp

    include <iostream>
    include "intSLLst.h"

    using namespace std;

    IntSLList::~IntSLList(){
    for(IntNode *p; !isEmpty();){
    p = head->next;
    delete head;
    head = p;
    }
    }

    void IntSLList::addToHeadLink(int el){
    head = new IntNode(el,head);
    if (tail == 0)
    tail = head;
    }

    void IntSLList::displayLink(){
    IntNode *temp;
    if (head == NULL)
    {
    cout<<"The List is Empty"<<endl;
    return;
    }
    temp = head;
    cout<<"Elements of list are: "<<endl;
    while (temp != NULL)
    {
    cout<<temp->info<<"->";
    temp = temp->next;
    }
    cout<<"NULL"<<endl;
    }

    void IntSLList::sort(){
    IntNode *temp, *s;
    int value;
    if (head == NULL)
    {
    cout<<"The List is Empty"<<endl;
    return;
    }
    temp = head;
    while (temp != NULL)
    {
    for (s = temp->next;s !=NULL;s = s->next)
    {
    if (temp->info > s->info)
    {
    value = temp->info;
    temp->info = s->info;
    s->info = value;
    }
    }
    temp = temp->next;
    }
    }

    void IntSLList::merge(IntSLList obj1, IntSLList obj2)
    {
    IntNode *temp, *list3;
    int value=0;
    IntNode *list1 = obj1.head;
    IntNode *list2 = obj2.head;

    if (list1 == NULL) {
        temp = obj2.head;
    
    cout<<"Elements of list are: "<<endl;
    while (temp != NULL)
    {
        cout<<temp->info<<"->";
        temp = temp->next;
    }
    cout<<"NULL"<<endl;
    }
    else if (list2 == NULL) {
    temp = obj1.head;
    
    cout<<"Elements of list are: "<<endl;
    while (temp != NULL)
    {
        cout<<temp->info<<"->";
        temp = temp->next;
    }
    cout<<"NULL"<<endl;
    }
    
    else {
        while(list1->next!=0)
        {
    
            list1=list1->next;
        }
        list1->next=list2;
    }
    
    
    return;
    

    }

  • main.cpp

    include "intSLLst.h"
    include <iostream>

    using namespace std;

    int main()
    {
    IntSLList MyIntSLList1;
    IntSLList MyIntSLList2;
    IntSLList MyIntSLList3;

    int num1, num2, choice;
    //perform operation on Linked List1
    while(1)
    {
        cout << "select operation"<<endl;
        cout<<"1.Insert Node in Link1at beginning"<<endl;
        cout<<"2.Display Linked List1"<<endl;
        cout<<"3.Sort Linked List1"<<endl;
        cout<<"4.Insert Node in Link2 at beginning"<<endl;
        cout<<"5.Display Linked List2"<<endl;
        cout<<"6.Sort Linked List2"<<endl;
        cout<<"7.Merge"<<endl;
        cout<<"8.Exit"<<endl;
    
        cout<<"Enter your choice : ";
        cin>>choice;
        switch(choice)
        {
        case 1:
            cout<<"Inserting Node in Link1 at Beginning: "<<endl;
            cout << "enter value:"<<endl;
            cin >> num1;
            MyIntSLList1.addToHeadLink(num1);
            cout<<endl;
            break;
        case 2:
            cout << "Displaying Linked List1:"<< endl;
            MyIntSLList1.displayLink();
            break;
        case 3:
            cout<<"Sort Link List: "<<endl;
            MyIntSLList1.sort();
            cout<<endl;
            break;
         case 4:
            cout<<"Inserting Node in Link2 at Beginning: "<<endl;
            cout << "enter value:"<<endl;
            cin >> num2;
            MyIntSLList2.addToHeadLink(num2);
            cout<<endl;
            break;
        case 5:
            cout << "Displaying Linked List2:"<< endl;
            MyIntSLList2.displayLink();
            break;
        case 6:
            cout<<"Sort Link List: "<<endl;
            MyIntSLList2.sort();
            cout<<endl;
            break;
        case 7:
            cout<<"Merged Linked list:"<<endl;
            MyIntSLList3.merge(MyIntSLList1, MyIntSLList2);
            MyIntSLList3.displayLink();
            cout<<endl;
            break;
        case 8:
            cout<<"Exiting..."<<endl;
            exit(1);
            break;  
        }
    }
    
    
    system("pause");
    return 0;
    

    }

Since you have a list3 listed I assume you want to create a third list representing the merged lists, leaving the initial lists intact.

So:
1) let curr1 work down list1
2) let curr2 work down list2
3) let curr3 work down list3

4)initialize curr1 and curr2 to be the head node of each respective list.

5) while curr1 and curr2 not null
6) if curr1 less than or equal to curr2, then add value of curr1 to list3 and move curr1 to next node in list1
7) else add value of curr2 to list3 and move curr2 to next node in list2

8) when the above loop ends determine which initial list ended first and add the value of the nodes of the list with nodes still in it to the end of the list3.

Hi Lerner ,thanks for the reply.
I tried using this but how can I get the values of linked list passed inside merge function from main function. I am passing objects directly but that I am not able to access in definition of merge function in file intSLLst.cpp. Can you please help me passing and accessing these linked list inside definition of merge function with code?

If I understand you right you've got three possible options, as I see it.

1) you can declare merge() as a member function that mutates "this".

2) you can declare an independent function that uses three lists, two that are not mutated, and one that is.

3) you might be able to declare a freind function that takes two lists and returns a third, but can't say that I've ever done it that way.

Of these I prefer either number one or number two. If you want to maintain the to passed lists and generate a third that is made by merging the values in the nodes of the passed lists, then I prefer number two.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.