单链表笔试题（是否相交，求交点；是否有环，求入环点）C++

1. 判断两个单链表是否相交，若相交求交点。

（1）首先仅判断是否相交？

方法：令两个单链表均走到末尾，看两者尾结点是否相同即可。

（2）判断是否相交+求交点。（此处已知单链表构造）

方法：先让较长的链表走(两个链表长度之差)步，若两个指针不相等且任一指针!=NULL就一同向后走，如果退出循环是两者相等则返回（相等的指针指向两个单链表交点）；否则返回NULL。

代码如下：

struct Node
{
	Node(int val):data(val),next(NULL){}//带参构造函数
	Node(){}//无参构造函数
	int data;
	Node* next;
};
int Get_length(Node* p)
{
	int count = 0;
	while (p != NULL)
	{
		count++;
		p = p->next;
	}
	return count;
}
Node* Get_Node(Node* headA, Node* headB)
{
	int len = Get_length(headA) - Get_length(headB);//已知headA指向的单链表较长
	for (int i = 0; i < len; ++i)
	{
		headA = headA->next;//较长单链表先走长度差值步
	}
	while (headA!=headB&&headA!=NULL)//两者不相等且任意一者不为空（由于两者剩余长度相同），则一同往后走
	{
		headA = headA->next;
		headB = headB->next;
	}
	if (headA == headB) return headA;
	else return NULL;
}
void main()
{
	//已知较长单链表：1 2 3 5 8 9 10
	//已知较短单链表：4 6 9 10
	Node a(1), b(2), c(3), d(5), e(8), f(9), g(10);//调用带参构造函数初始化节点
	Node x(4), y(6);
 
	Node* headA = &a;
	a.next = &b;
	b.next = &c;
	c.next = &d;
	d.next = &e;
	e.next = &f;
	f.next = &g;
 
	Node* headB = &x;
	x.next = &y;
	y.next = &f;//令两个单链表相交
	
	Node* h = Get_Node(headA, headB);
	if (h != NULL)
	{
		cout << "两个单链表相交，且交点为：" << h->data << endl;
	}
	else cout << "两个单链表不相交" << endl;
}

 示例：两个链表相交（如图）

  示例：两个链表不相交（如图）

2. 判断单链表是否有环，若存在环 则返回入环点。

（1）判断是否存在环：

【快慢指针法】快指针fast初始化从头结点向后走两步，慢指针slow初始化走一步。while(fast!=slow&&fast!=NULL)就让fast走两步，slow走一步。若退出循环是二者相等：代表有环存在。

注意：在while循环要判断fast!=NULL是由于如果单链表不存在环，则fast指针会先走到末尾结束循环。也保证了在while循环中fast走两步时不会出现空指针指向。

（2）求入环点（如图）

代码如下：

struct Node
{
	Node(int val):data(val),next(NULL){}
	Node(){}
	int data;
	Node* next;
};
Node* Get_Cir_Node(Node* head)
{
	//快慢指针
	Node* fast = head->next->next;//快指针初始化走两步
	Node* slow = head->next;
	
	//判断是否存在环？
	while (fast != slow && fast != NULL)//如果单链表不存在环，则fast指针会先走到末尾结束循环。也保证了在while循环中fast走两步时不会出现空指针指向。
	{
		fast = fast->next->next;
		slow = slow->next;
	}
	if (fast == NULL) return NULL;
	
	//有环，找入环点：x=z+(n-1)(y+z); 距离相同，速度相同~同时相遇在入环点
	Node* p = head;
	Node* q = fast;//或者Node*q=slow; 此刻fast和slow均指向快慢指针相遇点
	while (p != q)
	{
		p = p->next;
		q = q->next;
	}
	return p;
}
void main()
{
	//带环单链表：1 2 3 4 5 6 4
	Node a(1), b(2), c(3), d(4), e(5), f(6);
	Node* head = &a;
	a.next = &b;
	b.next = &c;
	c.next = &d;
	d.next = &e;
	e.next = &f;
	f.next = &d;//构成环
 
	Node* p = Get_Cir_Node(head);
	if (p != NULL) cout << "该单链表有环，入环点为：" << p->data << endl;
	else cout << "该单链表无环" << endl;
}

 示例：单链表有环（如图）

 示例：单链表无环（如图）