Icoding题解线性表合并

题干

链表合并

设线性表A=(a1, a2,…,am)，B=(b1, b2,…,bn)，试写一个按下列规则合并A、B为线性表C的算法，使得：
C= (a1, b1,…,am, bm, bm+1, …,bn) 当m≤n时；
或者
C= (a1, b1,…,an, bn, an+1, …,am) 当m>n时。
线性表A、B、C均以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。
函数的原型如下：
void lnk_merge(LinkList A, LinkList B, LinkList C)
即将A和B合并为C，其中 C 已经被初始化为空单链表
相关定义如下：

struct _lnklist{
ElemType data;
struct _lnklist *next;
};

typedef struct _lnklist Node;
typedef struct _lnklist *LinkList;

分析

简要分析题干：
题目的意思是，有链表A和链表B，A和B的结点数均未知，要求是将A和B合并为链表C。
合并的要求是：
1. 满足A链表中的结点和B链表中的结点交替连接
2. 假如有一个链表的结点数过多，不满足交替连接，那么就直接将多余的部分接在合并的链表之后
3. 要求用原来的结点合并链表，不要重新分配空间并复制原链表的数据
值得注意的问题：
1. 交替连接链表
2. 处理多余结点
3. 使用原结点合并
4. 链表有空的头结点
解题思路：
1. 使用三个指针，一个指针跟踪A链表第一个未被合并到C的结点，一个指针跟踪B链表第一个未被合并到C的结点，还有一个跟踪新链表即C链表的最新结点。
2. 使用一个循环，先连接A链表的一个结点，再连接B链表的一个结点。
3. 处理A中多出来的结点，处理B中多出来的结点

核心代码

首先声明三个指针，分别代表指向A、B、C链表的指针
这里需要注意，链表A，链表B均具有空的头节点
1
2
3
Node* CurrPtrC = C;
Node* CurrPtrA = A->next;
Node* CurrPtrB = B->next;

然后开始合并链表。
一旦指向A的指针或指向B的指针中有一方为空，我们就知道，有一个链表走到了尽头。
我们的循环要做的事情，就是保证A、B链表中的结点交替连接，直到一个链表的结点用完。
循环进行条件：指向A链表节点和指向B链表节点的指针均不为空。

while (CurrPtrA && CurrPtrB) {
        //将A的结点地址交给C指针的指向结点的next域
        CurrPtrC->next = CurrPtrA;
        //此时A的结点地址已被保存，我们将A指针指向下一个A链表的结点
        CurrPtrA = CurrPtrA->next;
        //然后，更新C指针，将其指向下一个结点
        //用这种方式，我们可以保证C指针始终指向C链表最新的一个结点
        CurrPtrC->next = CurrPtrC;

        //与上同理
        CurrPtrB->next = CurrPtrB;
        CurrPtrB = CurrPtrB->next;
        CurrPtrC->next = CurrPtrC;
}

至此，我们在一次循环中，交替链接了A链表的一个结点、B链表的一个结点.
同时，A指针指向A链表的下一个结点，B指针指向B链表的下一个结点.
C指针指向最新的结点，也就是B链表中的一个结点.
这样，我们每次循环都先后分别连接A、B两个链表中的一个结点.

然后，我们处理循环中没有处理完成的链表.
如果A指针不为空，说明A链表有剩余结点.
与前面的循环同理，不过除了笔者这种方法，也有更好的方法可以解决.
比如说，一行 CurrPtrC->next = CurrPtrA 即可一劳永逸地解决，根本不需要循环.

while (CurrPtrA) {
    CurrPtrC->next = CurrPtrA;
    CurrPtrA = CurrPtrA->next;
    CurrPtrC = CurrPtrC->next;
}

//与上同理，如果B指针不为空，说明B链表有剩余结点
while (CurrPtrB) {
    CurrPtrC->next = CurrPtrB;
    CurrPtrB = CurrPtrB->next;
    CurrPtrC = CurrPtrC->next;
}

完整代码

void lnk_merge(LinkList A, LinkList B, LinkList C) {
    Node* temp = C;
    Node* tempA = A->next;
    Node* tempB = B->next;
    
    while(tempA != NULL && tempB != NULL)
    {
        temp->next = tempA;
        temp = temp->next;
        tempA = tempA->next;
        
        temp->next = tempB;
        temp = temp->next;
        tempB = tempB->next;
    }

    while (tempA != NULL) {
        temp->next = tempA;
        temp = temp->next;
        tempA = tempA->next;
    }

    while (tempB != NULL) {
        temp->next = tempB;
        temp = temp->next;
        tempB = tempB->next;
    }
    
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。

Icoding题解 线性表 合并

题干

分析

核心代码

完整代码

Icoding题解线性表合并