CODEWITHSUNDEEP
c++linked-list
ck22
ck22

Reputation: 61

Union of two linked list- C++

Any assistance will be helpful. I have written a code to find the union of two linked list. However, I am getting an infinite loop at one section. I indicate it in the code. Please help me identify the error. Thanks.

//Finds the union of two linked lists. 
nodeType* unionLL(nodeType *&headA, nodeType *&headB)
{
      nodeType *tempA, *tempB, *newNode;         
      tempA = headA;
      tempB = headB;
      bool match = false;

      while (tempB -> link != NULL)
      {
            while (tempA -> link != NULL)                
            {
                  outfile <<"The infinite loop occurs here " << endl;
                  if (tempB -> intVal == tempA -> intVal)
                  {   
                      match = true;
                  }  
                  tempA = tempA -> link;
            }

            if (!match)
            {
               newNode = new nodeType;
               newNode -> intVal = tempB -> intVal;
               newNode -> link = NULL;
               tempA -> link = newNode;
            }
            tempA = headB;
            tempB = tempB -> link;
      }

      return headB;
 }

Upvotes: 2

Views: 2408

Answers (2)

txomon
txomon

Reputation: 662

I think you are not checking if it matches in tempA loop (neither in B's)

Upvotes: 0

Jonathan Leffler
Jonathan Leffler

Reputation: 753565

You have not identified whether the linked lists are sorted or not - so we should assume not. You have not identified which list can be modified; superficially, both lists could be modified by the function. You return headB which suggests that the result should be that the result set accessible from headB should contain every element in that list, plus a new element for each element accessible from headA that is not already found via headB.

Superficially, then, your pseudo-code should be:

foreach element in listA
    if (element not found in listB)
        add copy of element to listB

leaving listA untouched. Your code does not implement this logic.

Upvotes: 4

Related Questions