C++ – Merge non-sentinel linked list not working as intended [duplicate]

  algorithm, c++, data-structures, linked-list, merge

I am currently lost inside my logic for a Merge function that I am working on currently. I did the logic but it does not seem to be working. I am currently playing with non-sentinel linked lists for my practice. I’ll be posting my Merge function here so that you guys can take a look and I’ll post my entire source code (if you want to look further into it) in a Pastebin.

This logic never comes out of the while loop, just stays in there. I want it to transfer the other list’s node to the current list before the loop ends and sort the current list at the end when all the nodes from the other list are unlinked and linked to the current list.

I am trying to tackle this ques/function –

void merge(SortedList& other);
This function merges the nodes of other into the current list such that the current list stays sorted. If the value of two nodes are the same in the two lists, the nodes in the current list are placed before those of other

For example:

In the example below

Initial current list: {1, 1, 2, 4}, Initial other list: {3,4,5,8,9,10}

Final current list: {1,1,2,3,4,4,5,8,9,10}, final other list: {}

This function must be implemented by putting existing nodes together (as opposed to inserting the values of other as new nodes into the current list).

This is the question that I am trying to tackle. I just want to know where in my code I am wrong and how do I fix it.

Heres the merge function that I wrote –

template <typename T>
void SortedList<T>::merge(SortedList& other)
{
    
    if (other.front == nullptr)
        return;

    if (front == nullptr) {
        front = other.front; //first node
        back = other.back;// last node
        size_ = other.size_;
        other.front = nullptr;
        other.back = nullptr;
        other.size_ = 0;
        
    }
    else {
        Node* temp;
        Node* temp1 = front;
        //Node *temp2 = other.front;
        while (other.front && temp1)
        {
            if ( (temp1->dat < other.front->dat) || (temp1->dat == other.front->dat))
            {
                

                if (other.front != nullptr)
                {
                    temp = other.front;
                    temp->prev = temp1->prev;
                    temp->next = temp1->next;
                    temp1->next = temp;


                    Node* rm = other.front;
                    other.front = rm->next;
                    if (other.front != nullptr)
                    {
                        other.front->prev = nullptr;
                    }
                    else
                    {
                        other.back = nullptr;
                    }
                    rm = nullptr;
                }

            }
            if (temp1->next) { temp1 = temp1->next; }
            else { temp1 = nullptr; }
        }

    }
    other.front = nullptr;
    other.back = nullptr;
 }

Hope I got to ask my question clearly and sorry if my question was not clear. Thank you for your time!

Pastebin linkhttps://pastebin.com/BpagcFeU

Thank you!

Source: Windows Questions C++

LEAVE A COMMENT