c++ - 通过递归将两个链表合并为第三个链表 - C++

Question

所以基本上，我必须将两个链表(作为参数传递)合并到第三个链表(也作为参数传递) - 但在函数结束时，新列表仍必须排序，另一个链接列表必须为空。我很确定我很接近，但出于某种原因，我认为第三个列表的计算不正确。考虑到我不擅长递归，如果有人能看一看并告诉我我哪里错了，那就太棒了。最后，headX 和 headY 应该都是空的，它们的所有项目都在 headZ 中排序。但是，功能完成后，headZ 不正确(虽然我不确定为什么)。

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;
}

Answer 1

update - 你需要在合并排序过程中推进 headX 或 headY。也可以简化空列表检查。这个例子似乎有效:

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;
}