时间戳

首页 > 解决方案 > 合并2个链表没有困难

c - 合并2个链表没有困难

问题描述

我正在尝试编写一个将合并 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;
}

标签： clinked-list

解决方案

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

推荐阅读