Объединить 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

Вы можете удалить lastPtr, используя переменную Node ** (или NodePtr *), чтобы указать ссылку ->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;
}