如何递归地将2个有序链表合并成一个新的有序链表？

Question

这是我在这里的第一篇文章。我在递归合并两个链表时遇到了麻烦。很明显，即使经过大量的研究，我对链表/指针的理解还不够深入。这非常令人沮丧。下面是我不能工作的(可怕的)代码：

void SortedMergeRecur(Node*& xHead, Node*& yHead, Node*& zHead){

    if (xHead == 0 && yHead == 0){ //empty list
        return;
    }

    else if (xHead != 0 && yHead == 0){ //if y empty, put x into new
        zHead = xHead;
        zHead->link = xHead->link;
        return SortedMergeRecur(xHead->link, yHead, zHead->link);
    }

    else if (xHead == 0 && yHead != 0){ //if x empty, put y into new
        zHead = yHead;
        zHead->link = yHead->link;
        return SortedMergeRecur(xHead, yHead->link, zHead->link);
    }

    else { //niether empty
        if (xHead->data <= yHead->data){
            zHead = xHead;
            zHead = zHead->link;
            zHead->data = yHead->link->data;
            zHead = zHead->link;
            return SortedMergeRecur(xHead->link, yHead->link, zHead);
        }

        else {
            zHead = yHead;
            zHead = zHead->link;
            zHead->data = xHead->link->data;
            zHead = zHead->link;
            return SortedMergeRecur(xHead->link, yHead->link, zHead);
        }
    }
}

链表被定义为这个结构：

struct Node
{
   int data;
   Node *link;
};

我感到困惑、沮丧和迷失。现在我们将非常感谢您的帮助。我理解这样做背后的逻辑，但我不知道如何以它们需要被操纵的方式来操纵指针。

Answer 1

我想通了。我通过函数调用传递了xHead->link或yHead->link (无论需要使用哪一个)，并在...之前递增zHead = zHead->link。我不知道为什么它现在起作用了，但确实起作用了。

void SortedMergeRecur(Node*& xHead, Node*& yHead, Node*& zHead){
    if (xHead == 0 && yHead == 0){ //empty lists
        return;
    }

    else if (xHead != 0 && yHead == 0){ //if y empty, put x into new
        zHead = xHead;
        zHead->link = xHead->link;
        xHead = xHead->link;
        return SortedMergeRecur(xHead, yHead, zHead->link);
    }

    else if (xHead == 0 && yHead != 0){ //if x empty, put y into new
        zHead = yHead;
        zHead->link = yHead->link;
        yHead = yHead->link;
        return SortedMergeRecur(xHead, yHead, zHead->link);
    }

    else { //niether empty
        if (xHead->data <= yHead->data){
            zHead = xHead;
            zHead->link = xHead->link;
            xHead = xHead->link;
            return SortedMergeRecur(xHead, yHead, zHead->link);
        }
        else {
            zHead = yHead;
            zHead->link = yHead->link;
            yHead = yHead->link;
            return SortedMergeRecur(xHead, yHead, zHead->link);
        }
    }
}