Merge sort two linked list into a third linked list via recursion - c++

Question

So basically, I have to merge two linked lists (passed as parameters) into a third linked list (also passed in as a parameter) - but by the end of the function the new list must still be sorted and the other linked lists must be empty. I'm pretty sure I'm close, but for some reason I don't think the third list is being computed correctly. If anyone could take a look and tell me where I'm wrong real quick that would be awesome, considering I'm not to good at recursion. By the end, headX and headY should be both be empty, with all of their items sorted in headZ. However, after the function is done, headZ is not correct (though I'm not sure why).

void   sortedMergeRecur(Node* &headX, Node* &headY, Node* &headZ)
{
  // we can assume that both headx and heady are sorted linkedlists

  // first establish base case or when to stop
  if((headX == 0) && (headY != 0))
  {
    // x is empty, but y is not
    headZ = headY;
    headY = 0;
    return;
  }
  else if((headY == 0) && (headX != 0))
  {
    // y is empty, but x is not
    headZ = headX;
    headX = 0;
    return;
  }
  else if((headY == 0) && (headX == 0))
  {
    // if they're both empty, we don't need to add anything z
    headZ = 0;
    return;
  }

  // Pick either x or y to add
  if (headX->data <= headY->data)
  {
    headZ = headX;
    SortedMergeRecur(headX->link, headY, headZ->link);
    headX = 0;
  }
  else // if(headX->data > headY->data)
  {
    headZ = headY;
    SortedMergeRecur(headX, headY->link, headZ->link);
    headY = 0;
  }



  return;
}

I don't see any obvious problems. Are you forced to write your code taking references to pointers like that? It makes the code harder to understand. Try rewriting it as a function that takes pointers by value and returns pointers. — japreiss
– japreiss, Commented Nov 13, 2014 at 23:10
Unfortunately yes... In assignment description it says pass all three list heads through the function and it must be void. — Eric Diviney
– Eric Diviney, Commented Nov 13, 2014 at 23:20
Haven't figured out the cause yet but I can make your code go into infinite recursion with the inputs Node *x = new Node{ 1, new Node{ 7, nullptr } }; Node *y = new Node{ 0, new Node{ 7, new Node{ 7, nullptr } } }; (you'll need a C++11 compiler for that) — japreiss
– japreiss, Commented Nov 13, 2014 at 23:24
Interesting... In my driver file (that was supplied for my assignment) it just states that the z linked list has only 1 item in it, but it expects more than that and it aborts the program. — Eric Diviney
– Eric Diviney, Commented Nov 13, 2014 at 23:25

rcgldr · Accepted Answer · 2014-11-14 02:35:02Z

1

update - you need to advance headX or headY during the merge sort. Also the empty lists checks can be simplfied. This example seems to work:

void SortedMergeRecur(Node* &headX, Node* &headY, Node* &headZ)
{
    // assume that both headX and headY are sorted linkedlists
    // check for empty lists
    if(headX == 0)
    {
        headZ = headY;
        headY = 0;
        return;
    }
    if(headY == 0)
    {
        headZ = headX;
        headX = 0;
        return;
    }
    // move smaller of X,Y to Z
    if (headX->data <= headY->data)
    {
        headZ = headX;
        headX = headX->link;
        SortedMergeRecur(headX, headY, headZ->link);
    }
    else
    {
        headZ = headY;
        headY = headY->link;
        SortedMergeRecur(headX, headY, headZ->link);
    }
    return;
}

edited Nov 14, 2014 at 2:35

answered Nov 14, 2014 at 0:46

rcgldr

29.4k3 gold badges41 silver badges70 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Eric Diviney Over a year ago

Well, actually only the first call of the function modifies the original headZ pointer. After that, the function calls (the recursive calls) are all passing headZ->link, and not headZ itself.

Eric Diviney Over a year ago

Ahhh! You got it! Thank you so much for taking the time to look at that. I really appreciate you helping me out!

Collectives™ on Stack Overflow

Merge sort two linked list into a third linked list via recursion - c++

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related