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

链表有序表的合并

思路图

将链表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;
}