两个单向循环链表的合并(带头结点)
问题引入：
已知两个带头结点的单向循环链表，LA和LB分别是链表的头指针，LA=(a1,a2…am),LB=(b1,b2,…bm),编写算法，将LA和LB合并成一个单项循环链表LC=(a1,a2…am,b1,b2,…bm)。
核心算法：
只需要修改两个表的表尾结点让两个表连起来即可。最后释放多余的LB这个头结点
typedef struct node {
DataType data;
struct node *next;
}*LSNode;
//两个带头结点的单向循环链表合并
LSNode merge(LSNode LA, LSNode LB) {
LSNode pa = LA,LC=LA;
LSNode pb = LB;
while (pa->next != LA) {//让p指向LA表尾
pa=pa->next;
}
while (pb->next != LB) {//让p指向LB表尾
pb = pb->next;
}
pa->next = LB->next;
pb->next = LC;
free(LB);
return LC;
}
完整测试(VS2017)
List.h
#pragma once
typedef struct node {
DataType data;
struct node *next;
}*LSNode;
//初始化
void Initiate(LSNode *head) {
(*head) = (LSNode)malloc(sizeof(struct node));
(*head)->next = (*head);
}
//插入函数
bool Insert(LSNode head,int i, DataType data) {
int j = -1;
LSNode p = head,q;
while (p->next != head && j < i - 1)//最终p指向第j-1个结点
{
p = p->next;
j++;
}
if (j != i - 1)
{
printf("插入位置出错!");
return false;
}
q = (LSNode)malloc(sizeof(struct node));
q->data = data;
q->next = p->next;
p->next = q;
return 1;
}
//遍历链表
void print(LSNode head)
{
LSNode p = head;
while (p->next != head) {
p = p->next;
printf("%d ", p->data);
}
printf("\n");
}
//两个带头结点的循环单链表合并
LSNode merge(LSNode LA, LSNode LB) {
LSNode pa = LA,LC=LA;
LSNode pb = LB;
while (pa->next != LA) {//让p指向LA表尾
pa=pa->next;
}
while (pb->next != LB) {//让p指向LB表尾
pb = pb->next;
}
pa->next = LB->next;
pb->next = LC;
free(LB);
return LC;
}
源.cpp
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef int DataType;
#include"List.h"
int main() {
LSNode head,head1,head2;
Initiate(&head);
Initiate(&head1);
Initiate(&head2);
for (int i = 0; i < 10; i++) {
Insert(head, i, i + 1);
Insert(head1, i, i + 11);
}
print(head);
print(head1);
//执行两个单项循环链表的合并
printf("执行两个带头结点单项循环链表的合并:\n");
head2 = merge(head, head1);
print(head2);
return 0;
}
测试结果：
