两个单向循环链表的合并(带头结点)

别团等shy哥发育

发布于 2023-02-27 10:45:55

5690

发布于 2023-02-27 10:45:55

文章被收录于专栏：全栈开发那些事

两个单向循环链表的合并(带头结点)

问题引入：

已知两个带头结点的单向循环链表，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;
}