C++链表合并与并集函数单独正常，同时执行触发无限循环问题

问题描述 #

实现了两个链表操作函数：mergeLL（有序合并）与unionLL（并集），单独调用其中一个函数时功能正常，但同时调用并输出结果时，代码会陷入无限循环，不确定是NULL处理问题还是函数本身存在缺陷。

相关代码 #

#include <iostream>
using namespace std;

struct Node{
    int num;
    Node *next;
};

Node * unionLL (Node * LA, Node * LB)
{
    if(LA == NULL)
    {
         return LB;
    }
    if(LB == NULL)
    {
        return LA;
    }
    Node *temp = NULL;//Creation of a node name temp as a place holder
    if(LA != NULL) // if LA is less than LB
    {
         temp = LA;
         temp->next = unionLL(LA->next, LB);
    }
    else if(LB != NULL)
    {
        temp = LB;
        temp->next = unionLL(LA,LB->next);
    }
    return temp;
}

Node * mergeLL (Node * LA, Node * LB) // method
{
    if(LA == NULL)
    {
         return LB;
    }
    if(LB == NULL)
    {
        return LA;
    }
    Node *temp = NULL;//Creation of a node name temp as a place holder
    if(LA->num<=LB->num) // if LA is less than LB
    {
          temp = LA;
         temp->next = mergeLL(LA->next, LB);
    }
    else if(LB->num<=LA->num)
    {
        temp = LB;
        temp->next = mergeLL(LA,LB->next);
    }
    return temp;
}

int main()
{
 // set 1
    Node *head = new Node(); // Creation of node
    Node *neighbor1 = new Node();
    Node *neighbor2 = new Node();
    Node *neighbor3 = new Node();

    neighbor3->num=11;
    neighbor2->num=8;
    neighbor1->num=5;
    head->num= 3; // head is leading node

    head->next =neighbor1;
    neighbor1->next = neighbor2;
    neighbor2->next = neighbor3;
    neighbor3->next = NULL;

 // set 2

    Node *head2 = new Node(); // Creation of node
    Node *neighbor6 = new Node(); 
    Node *neighbor7 = new Node(); 
    Node *neighbor8 = new Node(); 
    Node *neighbor9 = new Node(); 
    Node *neighbor10 = new Node(); 

    head2->num= 2; // head is leading node
    neighbor6->num=6; // neighbor points to num which value is 6
    neighbor7->num=8;
    neighbor8->num=9;
    neighbor9->num=22;
    neighbor10->num=24;

    head2->next =neighbor6; //link to next element
    neighbor6->next = neighbor7; 
    neighbor7->next = neighbor8; 
    neighbor8->next = neighbor9; 
    neighbor9->next = neighbor10; 
    neighbor10->next = NULL; 

    Node *head3 = head;
    Node *head4 = head2;

    Node *Merge = mergeLL(head,head2);
    cout<<"mergeLL(LA, LB) = ";
    while(Merge != NULL)
    {
      cout<<Merge->num; cout<<" "; //end is no new line
      Merge= Merge->next;
    }

   Node *unionLLL = unionLL(head3,head4);
    cout<<"unionLLL(LA, LB) = ";
    while(unionLLL != NULL)
    {
      cout<<unionLLL->num; cout<< " ";
      unionLLL= unionLLL->next;
    }

    return 0;
}

问题原因分析 #

1. mergeLL的原地修改破坏原链表结构
   mergeLL是原地修改原链表节点的next指针来实现合并的，调用mergeLL(head, head2)后，原链表head和head2的节点指针已经被篡改，比如原head节点的next不再指向原来的neighbor1，而是指向合并后的节点，导致原链表的结构完全被破坏。

2. unionLL调用时使用了已被破坏的原链表
   你保存的head3和head4是原链表的头指针，但此时原链表已经被mergeLL修改，链表内部出现了循环引用，当unionLL遍历这个被破坏的链表时，就会陷入无限循环。

3. unionLL的逻辑不符合并集定义
   当前的unionLL只是简单地把两个链表拼接成一个（一直遍历LA到末尾，再拼接LB），没有实现去重，根本不是真正的并集功能。

修复方案 #

方案1：创建新节点实现非原地操作（推荐） #

让mergeLL和unionLL都创建新的节点，不修改原链表的结构，这样原链表可以被多次使用：

修复后的mergeLL

Node* mergeLL(Node* LA, Node* LB) {
    if (LA == NULL) return LB;
    if (LB == NULL) return LA;

    Node* temp = new Node();
    if (LA->num <= LB->num) {
        temp->num = LA->num;
        temp->next = mergeLL(LA->next, LB);
    } else {
        temp->num = LB->num;
        temp->next = mergeLL(LA, LB->next);
    }
    return temp;
}

修复后的unionLL（实现真正的去重并集）

// 辅助函数：检查节点值是否已在链表中
bool isPresent(Node* head, int num) {
    while (head != NULL) {
        if (head->num == num) return true;
        head = head->next;
    }
    return false;
}

Node* unionLL(Node* LA, Node* LB) {
    Node* result = NULL;
    Node* tail = NULL;

    // 先添加LA中所有不重复的元素
    while (LA != NULL) {
        if (!isPresent(result, LA->num)) {
            Node* newNode = new Node();
            newNode->num = LA->num;
            newNode->next = NULL;
            if (result == NULL) {
                result = newNode;
                tail = newNode;
            } else {
                tail->next = newNode;
                tail = newNode;
            }
        }
        LA = LA->next;
    }

    // 再添加LB中不在LA里的元素
    while (LB != NULL) {
        if (!isPresent(result, LB->num)) {
            Node* newNode = new Node();
            newNode->num = LB->num;
            newNode->next = NULL;
            if (result == NULL) {
                result = newNode;
                tail = newNode;
            } else {
                tail->next = newNode;
                tail = newNode;
            }
        }
        LB = LB->next;
    }

    return result;
}

方案2：原地操作前复制原链表 #

如果必须使用原地修改的mergeLL，那么在调用mergeLL之前先复制原链表，用复制后的链表进行合并，保留原链表给unionLL使用：

// 辅助函数：复制链表
Node* copyList(Node* head) {
    if (head == NULL) return NULL;
    Node* newHead = new Node();
    newHead->num = head->num;
    newHead->next = copyList(head->next);
    return newHead;
}

// main函数中修改mergeLL的调用：
Node* copyHead = copyList(head);
Node* copyHead2 = copyList(head2);
Node* Merge = mergeLL(copyHead, copyHead2);

这样原链表head3和head4的结构不会被破坏，unionLL可以正常使用。

内容的提问来源于stack exchange，提问作者Giselle Garcia