数据结构—带头结点单循环链表的合并

单循环链表的合并

• 设两个单循环链表A和B（都带头结点，设A和B都非空），合并A和B的思路是:
• 将A最后一个结点的指针域指向B的第一个结点（即指向头结点后的那个结点，首元结点），然后将B的最后一个元素的指针域指向A的头结点，释放B的头结点。

• 算法：
  • 1.获取A的最后一个结点，设为p1;
  • 2.获取B的最后一个结点，设为p2;
  • 3.令p1的指针域指向B的第一个结点，p1->next=B(头)->next；
  • 4.令p2的指针域指向A的头结点，p2->next=A(头)。

void Combine(LinkList L1, LinkList L2) 
{
	LNode *p1;
	LNode *p2;
	p1 = L1->next;
	p2 = L2->next;
	LNode *s1;
	LNode *s2;
	
	while (p1 != L1) 
	{
		if (p1->next == L1) 
		{
			s1 = p1;    // s1指向表L1的最后一个结点 
			break;
		}
		p1 = p1->next;    // 指针后移 
	}
	while (p2 != L2) 
	{
		if (p2->next == L2) 
		{
			s2 = p2;//s2指向表L2的最后一个结点 
			break;
		}
		p2 = p2->next;//指针后移 
	}
	
	s1->next = L2->next;   // L1尾部接到L2首元结点
	delete(L2);  // 释放L2头结点
	s2->next = L1;   // L2尾部接到L1头结点
}
           

代码实现

• main.cpp

#include<iostream>

using namespace std;

typedef struct LNode 
{
	int data;
	struct LNode *next;
}LNode, *LinkList;

// 初始化 
int InitList(LinkList &L) 
{
	L = new LNode;
	L->next = L;
	return 1;
}

int ListLength(LinkList L) 
{
	int length = 0;
	LNode *p;
	p = L->next;
	
	while (p != L) 
	{
		p = p->next;
		length++;
	}

	return length;
}

void TraveList(LinkList L) 
{
	LNode *p;
	p = L->next;
	while (p != L) 
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}


// 尾插法创建单循环链表
void CreateList(LinkList &L, int n)
{
	L = new LNode;
	L->next = L;
	LNode *r;
	r = L;

	printf("请输入链表元素值:\n");
	for (int i = 0; i < n; i++)
	{
		printf("请输入第%d个元素的值:", i + 1);
		LNode *p;
		p = new LNode;
		scanf("%d", &p->data);
		p->next = L;
		r->next = p;
		r = p;
	}
}

void Combine(LinkList L1, LinkList L2) 
{
	LNode *p1;
	LNode *p2;
	p1 = L1->next;
	p2 = L2->next;
	LNode *s1;
	LNode *s2;
	
	while (p1 != L1) 
	{
		if (p1->next == L1) 
		{
			s1 = p1;    // s1指向表L1的最后一个结点 
			break;
		}
		p1 = p1->next;    // 指针后移 
	}
	while (p2 != L2) 
	{
		if (p2->next == L2) 
		{
			s2 = p2;//s2指向表L2的最后一个结点 
			break;
		}
		p2 = p2->next;//指针后移 
	}
	
	s1->next = L2->next;   // L1尾部接到L2首元结点
	delete(L2);  // 释放L2头结点
	s2->next = L1;   // L2尾部接到L1头结点
}

int main() 
{
	LinkList A;    // 链表A 
	LinkList B;   // 链表B 

	if (InitList(A)) 
	{
		printf("链表A初始化成功!\n");
	}
	else 
	{
		printf("链表A初始化失败!\n");
	}

	if (InitList(B)) 
	{
		printf("链表B初始化成功!\n");
	}
	else 
	{
		printf("链表B初始化失败!\n");
	}

	printf("请输入链表A的长度:");
	int n1;
	scanf("%d", &n1);
	CreateList(A, n1);
	printf("遍历链表A:\n");
	TraveList(A);

	printf("请输入链表B的长度:");
	int n2;
	scanf("%d", &n2);
	CreateList(B, n2);
	printf("遍历链表B:\n");
	TraveList(B);

	Combine(A, B);
	printf("合并后的链表:\n");
	TraveList(A);
	printf("合并后链表长度是:%d\n", ListLength(A));

	system("pause");

	return 0;
}
           

• 运行结果