轻松合并2个链表

Question

我正在尝试写一个函数，它将合并2个链表，并返回合并后的列表。我做到了，但我不得不使用lastPtr。问题是，最后一次while循环迭代创建了一个不必要的节点。因此，问题是我如何删除无用的lastPtr

下面是代码：

NodePtr merge(NodePtr s1, NodePtr s2)
{
    NodePtr s3, currPtr, lastPtr;
    s3 = malloc(sizeof(Node));
    currPtr = s3;

    while(s1 != NULL){
        currPtr->ch = s1->ch;
        currPtr->nextPtr = malloc(sizeof(Node));
        currPtr = currPtr->nextPtr;
        s1 = s1->nextPtr;
    }

    while(s2 != NULL){
        lastPtr = currPtr;
        currPtr->ch = s2->ch;
        currPtr->nextPtr = malloc(sizeof(Node));
        currPtr = currPtr->nextPtr;
        s2 = s2->nextPtr;
    }

    lastPtr->nextPtr = NULL;
    return s3;
}

Answer 1

您可以通过使用Node ** (或NodePtr *)变量指向lastPtr链接来删除->nextPtr。它还可以指向列表变量s3的头部。这允许在没有创建列表的第一个元素的特殊情况下实现代码：

NodePtr merge(NodePtr s1, NodePtr s2)
{
    NodePtr s3 = NULL;
    NodePtr *currPtrPtr = &s3;

    while(s1 != NULL){
        *currPtrPtr = malloc(sizeof(Node));
        (*currPtrPtr)->ch = s1->ch;
        currPtrPtr = &(*currPtrPtr)->nextPtr;
        s1 = s1->nextPtr;
    }

    while(s2 != NULL){
        *currPtrPtr = malloc(sizeof(Node));
        (*currPtrPtr)->ch = s2->ch;
        currPtrPtr = &(*currPtrPtr)->nextPtr;
        s2 = s2->nextPtr;
    }

    *currPtrPtr = NULL;
    return s3;
}