两个单链表相交问题1——环存在与否

1. 题目：

给定两个单链表的头节点head1和head2，这两个链表可能相交也可能不相交。实现一个函数，如果相交，返回相交的第一个节点，不相交返回NULL。
ps:单链表可能是有环，可能无环
有环的样子：
两个单链表相交问题1——环存在与否
无环的样子：

要求：链表1的长度是n，链表2长度m，时间复杂度O(m+n)，额外空间复杂度O(1)

2. 题目拆分：

问题1：如何判断一个链表是否有环，如果有，返回第一个进入环的节点如上图中的节点join，没有则返回NULL
解法：
再贴一下上面的图，方便理解
两个单链表相交问题1——环存在与否
从图中我们可以看出，如果有环则遍历的时候一定会在环中不停的转，而不存在环的时候则一定会遍历到末尾，遇到NULL指针
具体步骤：
（1）设置两个指针(slow、fast)均指向链表的头节点，slow每次走1步，fast每次走2步，开始遍历
（2）如果链表没有环，则fast指针最先到达NULL指针处，直接返回NULL
（3）如果链表有环，则slow和fast一定会在环中的某个位置相遇，此时fast重新指向head处，slow保持不动。然后二者开始均以每次 1 step移动，再次相遇的时候就是环的入口节点
证明如下：
两个单链表相交问题1——环存在与否
为什么会有L1 = C-L2呢？

证明：由图可知是在meet点处相遇，我们知道：
	slow指针走过的路程为：L1 + L2 = v*t
	fast指针走过的路程为：L1 + N*C + L2 = 2v*t，其中N为正整数
	∴ 2*(L1 + L2) = L1+N*C+L2
	∴ L1+L2 = N*C
	∴ L1 = N*C- L2

代码：

#include<bits/stdc++.h>
using namespace std;

typedef struct node
{
   int val;
   struct node* next;
}node;

void tail_insert(node *L, int n) {
	if(n <= 0){
		printf("num is error\n");
		return;
	}
    node *temp = L;
    node* loop = NULL;
    for(int i = 1; i <= n; i++)
    {
        node *new_node = (node*)malloc(sizeof(node));
        new_node->next = NULL;
        new_node->val = i;
        
        temp->next = new_node;
        temp = new_node;
        if(i == 3)
        {
        	loop = new_node;
		}
    }
    temp->next = loop;
}
node* getLoopEnter(node* head)
{
	if(head == NULL || head->next == NULL || head->next->next == NULL){
		return NULL;
	}
	node* slow = head;
	node* fast = head;
	slow = slow->next;
	fast = fast->next->next;	
	while(slow != fast){
		if(fast->next == NULL || fast->next->next == NULL){
			return NULL;
		}
		fast = fast->next->next;
		slow = slow->next;
	}
	fast = head;
	while(slow != fast){
		slow = slow->next;
		fast = fast->next;
	}
	return slow;
}

int getLoopLen(node* loop){
	int len = 1;
	node* tmp = loop->next;
	while(tmp != loop){
		tmp = tmp->next;
		len++;
	}
	return len;
}


int main()
{
    int n; 
    node* head =(node*) malloc(sizeof(node));
	head->next = NULL;
    //------------------tail_insert------------------//
    printf("Please Input Insert nums:");
    scanf("%d",&n);
    tail_insert(head,n);
    node* ans = getLoopEnter(head);
    if(ans){
    	printf("enter loop node's val is %d\n",ans->val);
    	printf("loop's len is %d\n",getLoopLen(ans));
	}else{
		printf("List is No loop\n");
	}
    //-----------------------------------------------//

    return 0;
}

test结果：
两个单链表相交问题1——环存在与否
感觉篇幅有点长，接下来的两篇分开写了。。。。。

问题2：如何判断两个无环链表相交，相交则返回第一个相交的节点，否则直接返回NULL
两个单链表相交问题2——无环链表相交
问题3：如何判断两个有环链表相交，相交则返回第一个相交的节点，否则直接返回NULL
两个单链表相交问题3——有环链表相交

两个单链表相交问题1——环存在与否

1. 题目：

2. 题目拆分：

相关推荐