[SOLVED] Linked list infinite loop c++

Issue

This Content is from Stack Overflow. Question asked by Giselle Garcia

I’ve created two linked lists it’s supposed to do a union and a merge. If I run the functions separately it does the task it’s supposed to do merge or union. But when I try to output both simultaneously, the code infinitely keeps going. I don’t know if it has to do with my null or the functions themselves.

#include <iostream>
using namespace std;

    struct Node{
    int num;
    Node *next;
    };

//

Node * unionLL (Node * LA, Node * LB)
{
 
      if(LA == NULL)
    {
         return LB;
    }
        if(LB == NULL)
        {
            return LA;
        }
        Node *temp = NULL;//Creation of a node name temp as a place holder
        if(LA != NULL) // if LA is less than LB
        {
             temp = LA;
             temp->next = unionLL(LA->next, LB);
        }
        else if(LB != NULL)
        {
            temp = LB;
            temp->next = unionLL(LA,LB->next);
        }
            return temp;
        
}


Node * mergeLL (Node * LA, Node * LB) // method
{
    if(LA == NULL)
    {
         return LB;
    }
        if(LB == NULL)
        {
            return LA;
        }
        Node *temp = NULL;//Creation of a node name temp as a place holder
        if(LA->num<=LB->num) // if LA is less than LB
        {
              temp = LA;
             temp->next = mergeLL(LA->next, LB);
        }
        else if(LB->num<=LA->num)
        {
            temp = LB;
            temp->next = mergeLL(LA,LB->next);
        }
            return temp;

}

int main()
{
 // set 1
    Node *head = new Node(); // Creation of node
    Node *neighbor1 = new Node();
    Node *neighbor2 = new Node();
    Node *neighbor3 = new Node();


    neighbor3->num=11;
    neighbor2->num=8;
    neighbor1->num=5;
    head->num= 3; // head is leading node

    head->next =neighbor1;
    neighbor1->next = neighbor2;
    neighbor2->next = neighbor3;
    neighbor3->next = NULL;

 // set 2

    Node *head2 = new Node(); // Creation of node
    Node *neighbor6 = new Node(); 
    Node *neighbor7 = new Node(); 
    Node *neighbor8 = new Node(); 
    Node *neighbor9 = new Node(); 
    Node *neighbor10 = new Node(); 

    head2->num= 2; // head is leading node
    neighbor6->num=6; // neighbor points to num which value is 6
    neighbor7->num=8;
    neighbor8->num=9;
    neighbor9->num=22;
    neighbor10->num=24;

    head2->next =neighbor6; //link to next element
    neighbor6->next = neighbor7; 
    neighbor7->next = neighbor8; 
    neighbor8->next = neighbor9; 
    neighbor9->next = neighbor10; 
    neighbor10->next = NULL; 

    Node *head3 = head;
    Node *head4 = head2;

    Node *Merge = mergeLL(head,head2);
    cout<<"mergeLL(LA, LB) = ";
    while(Merge != NULL)
    {
      cout<<Merge->num; cout<<" "; //end is no new line
      Merge= Merge->next;
    }




   Node *unionLLL = unionLL(head3,head4);
    cout<<"unionLLL(LA, LB) = ";
    while(unionLLL != NULL)
    {

      cout<<unionLLL->num; cout<< " ";
      unionLLL= unionLLL->next;
    }

    return 0;







}




Solution

You are modifying the original linked lists in your mergeLL and unionLL functions. This is done when you change ->next to point to a different Node then it originally did. It is making some circular loops where head points to head2 and that is why it never reaches the end. Your mergeLL and unionLL functions need to create new Node() inside there, so that the original lists stay intact. Just copying the head node as you do in main doesn’t preserve the original linked list order.

I’ve created a helpful printList function, that you can see the addresses, which can help you debug/design the linked list you want.

void printList(Node *head, const char *name)
{

    cout << name << ":";
    while (head != NULL)
    {
        cout << " " << head->num << "(" << head << ")";
        head = head->next;
    }
    cout << "\n";
}


int main {
...
    printList(head, "head");
    printList(head2, "head2");
    Node *Merge = mergeLL(head, head2);
    printList(Merge, "mergeLL(LA, LB)");
    printList(head, "head");
    printList(head2, "head2");
...

}




returns

head: 3(0x1817eb0) 5(0x1817ed0) 8(0x1817ef0) 11(0x1817f10)
head2: 2(0x1817f30) 6(0x1817f50) 8(0x1817f70) 9(0x1817f90) 22(0x1817fb0) 24(0x1817fd0)
mergeLL(LA, LB): 2(0x1817f30) 3(0x1817eb0) 5(0x1817ed0) 6(0x1817f50) 8(0x1817ef0) 8(0x1817f70) 9(0x1817f90) 11(0x1817f10) 22(0x1817fb0) 24(0x1817fd0)
head: 3(0x1817eb0) 5(0x1817ed0) 6(0x1817f50) 8(0x1817ef0) 8(0x1817f70) 9(0x1817f90) 11(0x1817f10) 22(0x1817fb0) 24(0x1817fd0)
head2: 2(0x1817f30) 3(0x1817eb0) 5(0x1817ed0) 6(0x1817f50) 8(0x1817ef0) 8(0x1817f70) 9(0x1817f90) 11(0x1817f10) 22(0x1817fb0) 24(0x1817fd0)


This Question was asked in StackOverflow by Giselle Garcia and Answered by toppk It is licensed under the terms of CC BY-SA 2.5. - CC BY-SA 3.0. - CC BY-SA 4.0.

people found this article helpful. What about you?