【数据结构之线性表】有序表的合并（链表篇）

链表有序表的合并

思路图

将链表L1和L2按照顺序合并到L3中（注：三个链表都是带头结点的）

A、要实现有序合并，必须先比较L1,L2两表中结点的大小，这里我们暂时先不讨论，直接根据图中来进行思路整理，比如这里：L1后面的数比L2后边的数要小，所以我们先将L1后边的数插入到L3中，步骤如下：

其中：

指针q：指向要插入L3中的结点，这里

q=L1->next

指针p3：始终指向L3的最后一个结点，方便后续结点插入

 图中步骤如下：

①删除q指针指向结点前面的指针

L1->next=q->next

②删除q指针指向结点的后一个指针（相当于把q指向的结点给空出来）

q->next=NULL

③直接移动L3头结点的指针，把q所指的结点接在L3后面

p3->next=q

④移动p3，使得p3始终指向L3的最后一个结点，方便后续结点插入

p3=p3->next

A步总代码

 if (L1->next->data < L2->next->data) {
            struct Node *q = L1->next;
            L1->next = q->next;
            q->next = NULL;
            p3->next = q;
            p3 = p3->next;

 

B、接下来L2后面的值比L1后面的值（由于①中指针的移动，现在紧跟着L1的是数值为5的结点了）小，所以要插入L2后面的结点到L3中了，代码同上 

B步总代码

else if (L1->next->data > L2->next->data) {
            struct Node *q = L2->next;
            L2->next = q->next;
            q->next = NULL;
            p3->next = q;
            p3 = p3->next;
        }

C、当我们学会插入操作后，同时不难发现，如果两结点的数值相同，此时我们就可以任意插入一个链表的结点，然后把另一个链表中相同的结点free掉就行（为了确保L1、L2后面紧跟未插入过的结点）

C步总代码

else {
            struct Node *q = L1->next;
            L1->next = q->next;
            q->next = NULL;
            p3->next = q;
            p3 = p3->next;
            free(L2->next);
            L2->next = L2->next->next;//free操作过后记得移动指针位置
        }

D、我们发现，两表长度不一致，当一个链表变为空时，可以直接把另一个链表剩下的直接插入到L3中

D步总代码

if (L1->next == NULL) {
        p3->next = L2->next;
    } else {
        p3->next = L1->next;
    }

总体代码

#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
struct Node {
    ElementType data;
    struct Node *next;
};

void Sort_head(struct Node *L1, struct Node *L2) {
    struct Node *L3 = NULL;
    L3 = malloc(sizeof(struct Node));
    struct Node *p3 = L3;
    while (L1->next != NULL && L2->next != NULL) {
        if (L1->next->data < L2->next->data) {
            struct Node *q = L1->next;
            L1->next = q->next;
            q->next = NULL;
            p3->next = q;
            p3 = p3->next;
        } else if (L1->next->data > L2->next->data) {
            struct Node *q = L2->next;
            L2->next = q->next;
            q->next = NULL;
            p3->next = q;
            p3 = p3->next;
        } else {
            struct Node *q = L1->next;
            L1->next = q->next;
            q->next = NULL;
            p3->next = q;
            p3 = p3->next;
            free(L2->next);
            L2->next = L2->next->next;
        }
    }
    if (L1->next == NULL) {
        p3->next = L2->next;
    } else {
        p3->next = L1->next;
    }
}

int main() {
    struct Node *L1, *L2;//创建含头结点的空链表 
    L1 = malloc(sizeof(struct Node));
    L2 = malloc(sizeof(struct Node));
    L1->next = NULL;
    L2->next = NULL;

    printf("Enter the elements for list 1: ");
    for (int i = 0; i < 3; i++) {
        struct Node *newNode = malloc(sizeof(struct Node));//为链表1插入入元素 
        scanf("%d", &newNode->data);
        newNode->next = L1->next;
        L1->next = newNode;
    }

    printf("Enter the elements for list 2: ");
    for (int i = 0; i < 3; i++) {
        struct Node *newNode = malloc(sizeof(struct Node));//为链表2插入入元素 
        scanf("%d", &newNode->data);
        newNode->next = L2->next;
        L2->next = newNode;
    }
//完成插入工作后，进行合并 
    Sort_head(L1, L2);
    
//合并完成后进行遍历输出 
    printf("Merged list: ");
    struct Node *temp = L1->next;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }

    return 0;
}

注意事项

在Sort_head函数中，您需要确保L1和L2的头节点不为空，否则可能会导致空指针解引用错误

while (L1->next != NULL && L2->next != NULL) 

这样，我们的合并操作就实现啦~~希望能帮到您Hi~ o(*￣▽￣*)ブ

思考：

如何实现顺序表的合并呢？如果想要知道的话，请关注博主吧~~~主页为您解答！ 

原文地址：https://blog.csdn.net/2301_79982543/article/details/142498873

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！