单链表-两个线性表的合并1（破环原链表+尾插法）_令l1=(x1,x2,...xn),,l2=(y1,y2,...ym)是两个线性表,采用带头节点的单-CSDN博客

本文链接：https://blog.csdn.net/muyu_muyu/article/details/111500529

本文介绍了一种线性表合并算法，该算法采用破环原有链表的方式，将两个线性表L1和L2合并成一个新的线性表L3。具体实现包括定义指针遍历原链表并将节点按特定顺序插入新链表。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题意：
令L1 = (X1,X2,X3,X4…Xn), L2 = (y1,y2,y3,y4…ym);是两个线性表。采用带头节点的链表存储，设计一个算法合并L1,L2，结果放在线性表L3中，要求如下：
L3 = (X1,Y1,X2,Y2,X3,Y3,…XmYm,Xm+1,…Xn) 当m<= n
L3 = (X1,Y1,X2,Y2,X3,Y3,…XnYn,Yn+1,…Ym) 当n<= m
L3采用单链表存储。

单链表的存储结构：

typedef struct LinkList{
        int data;
        LinkList * next;
    }

分析：
这里是线性表的合并，如何合并呢？
这里有两种情况，分为：
1.破环原有链表
2.不破坏原有链表

这里是采用破环原有链表合并。

那破环原有链表是什么意思呢？
现在有L1.和L2链表，都带有头节点。
1.现在将两个头节点和两者其余部分分开。（画图更好理解）
2.一个头节点作为L3的头节点。另一个头节点释放free。
3.定义两个指针p,q，两者各指向两个链表其余部分，并将进行遍历。

所以，这种操作已经破环了链表。

思路：
1.定义两个指针各指向链表其余部分，定义一个尾指针。释放L2
2.通过while循环，条件为p!=null&&q!=null,再循环体中，将各自节点插入L3头节点后，各自遍历。
3.当等长节点遍历结束后，将多余部分链接到L3后，此时不知道是谁，先结束，但是，不管是q还是p，这里统一用p指向。
（如果两者等长，则刚好结束，r->next = null）
4.多余部分连接（r->next = p）

C代码实现：

void Merge1(LinkList * L1,LinkList * L2,LinkList *&L3){
       LinkList * p = L1->next,*q = L2->next,*t; //尾指针
       L3 = L1;
       r = L3;
       free(L2);
       while(p!=null && q!=null){
           r->next = p;t = p;p=p->next;
           r->next = q;t = q;q =q->next;
       }
       r->next = null; //如果两者刚好等长，刚好结束!
       if(q!=null)p = q; //统一p处理
       r->next = p; //连接其余节点
   }