带环相交链表问题_为什么环装链表求相交

设计目的：

掌握链表的基本操作。
掌握带环链表的相关操作算法。

总览效果效果：

需求分析

1需要带头结点的单链表，根据元素值输入对比，修改链域，形成新链表。
2快慢指针法或者标记数组两种方法。
3修改链域，恢复单链表，根据链表长度，遍历链表得到链表中间节点。
4分四种情况讨论链表相交情况。

概要设计

1struct node{数据域；链域；标记位；}
2void makecircle（double x,double y）//输入元素值成环
{ 1，找到值为x,y的指针；
2y的链域指向x，x链域指向空；
}
3void iscircle（）//标记数组法
{1，将节点标记位置为1；
2，遍历链表，并修改节点标志位为0；
3，判断节点的下一节点的标记位若为0，则有环，否则无环。
}
Void Iscircle（）//快慢指针法
{ 1，快指针每次前进2，慢指针每次前进1；
2，快慢指针若相等，则有环，否则无环。
}
4 void notcircle（）
{1,修改链域，恢复成单链表；
2，第一遍遍历链表，求出链表节点个数；
3，第二遍遍历链表，求出中间节点位置指针；
}
5
Nodeischarge（）
{（ 1）一个链表有环，一个链表无环，则两链表不相交。
（2）两个链表均有环，用一个链表快慢指针的相遇点去遍历，若遇到另一个链表的相遇点则相交，共用一个环，否则不相交。
（3）两个链表相交，交点在环外，修改链域转化为不带环的两个单链表求交点。
（4）两个链表相交，交点在环上。
}
Node entrynode()//得到环路入口位置
{根据追及相遇问题模型，头指针和快慢指针相遇点每次进一，最后相等的位置即为环路入口位置。}

详细设计

1，if (temp1 > temp2)
	{
		node* p;
		p = p2;
		p2 = p1;
		p1 = p;
	}//始终令p1指向先出现得节点
newfirst = new node;
	newfirst->link = p2->link;//新头节点指向p2得后续节点
	p2->link = p1;//成环
2，while (current != NULL){
if (current->link->flag == 0){
			current->flag = 1;
			current = current->link;// 遍历过程中修改标志位
		}
		else if (current->link->flag == 1){
			n = current;
			m = current->link;// 返回环路起点 终点
			return true;
		}
while (fast != NULL && fast->link != NULL)//快指针先为空，则为单链表无环
	{   slow = slow->link; //慢指针每次前进一步
		fast = fast->link->link;//快指针每次前进两步
		if (slow == fast) //相遇，存在环
			break;
	}
	if (fast && fast->link) return fast;
3，	   int cnt = 0;//计数器
		while (current != NULL){
			cnt++;
			current = current->link;
		}//若有偶数个节点 输出中间两个  若有奇数个节点 输出正中间得
		current = first->link;	
		int i = 0;
		while (current != NULL){
			i++;
			if (i == (cnt / 2)) break;
			else current = current->link;}
4，node* circlenode1 = Iscircle(p);
	node* circlenode2 = Iscircle(q);
	if (circlenode1 == NULL || circlenode1 == NULL) return NULL;//第一种情况，如果其中任意一条链不带环 则不相交
while (current != circlenode1 && current != circlenode2) current = current->link;
	if (current != circlenode2) return NULL;//第二种情况，都有环，用一个相遇点去遍历，未遇到另一个相遇点，则不相交。
	node* entry1 = entrynode(p, circlenode1);
	node* entry2 = entrynode(q, circlenode2);
if (entry1 == entry2)//情况3，将环去掉，转化为两个单链表相交，求交点
	{
		while (current1 != NULL){
			while (current2 != NULL){
				if (current1 == current2)
					return current1;
				else current2 = current2->link;
			}
			current2 = q;
			current1 = current->link;
		}
	}
//第四种情况，两个入口点，任意返回
	return entry1;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60