c++ - 合并两个排序的链表

Question

我正在尝试合并两个已排序的链表。在这里我只是想实现我自己的算法。当然网上有很多解决方案。代码是:

Node* MergeLists(Node *headA, Node* headB)
{
    int countA = 0, countB = 0;
    while(headA){countA++; headA = headA->next;}
    while(headB){countB++; headB = headB->next;}
    Node *res, *tres;
    res = new Node();
    res->next = NULL;
    tres = res;
    for(int i = 0; i < countA+countB-1; i++)
    {
        Node* temp = new Node();
        temp->next = NULL;
        tres->next = temp;
        tres = tres->next;
    }
    while(headA != NULL && headB != NULL)
    {
        if(headA->data > headB->data)
        {
            res->data = headB->data;
            res = res->next;
            headB = headB->next;
        }
        else if(headA->data < headB->data)
        {
            res->data = headA->data;
            res = res->next;
            headA = headA->next;
        }
    }
    while(headA)
    {
        res = headA;
    }
    while(headB)
    {
        res = headB;
    }
    return res;
}

这只是一个返回合并链表头地址的函数。

考虑这个输入/输出示例:

Input (stdin):

3
4
1 3 5 6
3
2 4 7
1
15
1
12
0
2
1 2

My Output (stdout)

0 0 0 0 0 0 0
0 0
0 0

Expected Output
1 2 3 4 5 6 7
12 15
1 2

因此，我的输出全为零。这是由于这段代码的问题:

Node *res, *tres;
    res = new Node();
    res->next = NULL;
    tres = res;
    for(int i = 0; i < countA+countB-1; i++)// this is creating a new linked list.
    {
        Node* temp = new Node();
        temp->next = NULL;
        tres->next = temp;
        tres = tres->next;
    }

我认为 tres 和 res 之间的联系没有正确发生。你能告诉我如何解决这个问题吗？

更新:

Node* MergeLists(Node *headA, Node* headB)
{

    int countA = 0, countB = 0;
    Node* tempA, *tempB;
    tempA = headA; tempB = headB;
    while(headA){countA++; tempA = tempA->next;}
    while(headB){countB++; tempB = tempB->next;}
    Node *res, *tres;
    res = new Node();
    res->next = NULL;
    tres = res;
    for(int i = 0; i < countA+countB-1; i++)
    {
        Node* temp = new Node();
        temp->next = NULL;
        tres->next = temp;
        tres = tres->next;
    }
    while(headA != NULL && headB != NULL)
    {
        if(headA->data > headB->data)
        {
            res->data = headB->data;
            res = res->next;
            headB = headB->next;
        }
        else if(headA->data < headB->data)
        {
            res->data = headA->data;
            res = res->next;
            headA = headA->next;
        }
    }
    if(headA)
    {
        res= headA;
        //res = res->next;
        //headA = headA->next;
    }
    if(headB)
    {
        res = headB;
        //res = res->next;
        //headB = headB->next;
    }
    return res;
}

这次 ~ stdout 没有响应~

Answer 1

问题出在这部分代码上。

while(headA){countA++; headA = headA->next;}
while(headB){countB++; headB = headB->next;}

这个循环执行完后，headA & headB 都指向了NULL； 所以当

while(headA != NULL && headB != NULL)

循环开始，它甚至没有进入循环。由于这个循环负责赋值，所以不进入这个循环。因此，您的所有值都设置为默认值 0。

正如@Slava 提到的，您甚至不需要这个循环。由于您直接遍历节点并且可以在出现 NULL 时停止。

创建一个临时指针并使用该指针计算 countA 和 countB。

有点像

Node* temp;
temp = headA;
while(temp){countA++; temp = temp->next;}
temp = headB;
while(temp){countB++; temp = temp->next;}

此外，这可能会导致无限循环。请增加循环内的节点。或者只是将条件更改为 if，而不是 while。

    while(headA)
    {
        res = headA;
    }
    while(headB)
    {
        res = headB;
    }

更新-

另一个问题: 计算后返回的 res 指向最后一个元素。因此输出将只是一位数字。

你能做的是

tres = res;
for(int i = 0; i < countA+countB-1; i++)
{
    ...
}
tres = res; // Add this line, so your keeping track of the original head
while(headA != NULL && headB != NULL)

最后 return tres; 而不是 return res;有了这个，您将返回原来的头部。