链表问题（1）

两个链表相交的一系列问题

1）判断单链表是否有环 有环返回第一个入环节点  无环返回NULL

#include<iostream>
#include<hash_set>
using namespace std;

typedef struct Node
{
	int data;
	Node* next;
};

typedef struct
{
	Node* head;
	int count;
}Linklist, *pList;

Node* YouHuan(Node* head)//快慢指针
{
	if (head == NULL || head->next == NULL || head->next->next == NULL)
	{
		return NULL;
	}
	 
	Node* fast = head;
	Node* slow = head;
	while (fast != slow)
	{
		if (fast->next == NULL || fast->next->next == NULL)
		{
			return NULL;
		}
		fast = fast->next->next;
		slow = slow->next;
	}
	fast = head;
	while (fast != slow)
	{
		fast = fast->next;
		slow = slow->next;
	}
	return slow;
}

//hash_set解法

Node* YouHuan2(Node* head)
{
	hash_set<Node*>   hs;
	Node* p = head;
	while (p->next)
	{
		hs.insert(p);
		p = p->next;
		hash_set<Node*>::iterator beg = hs.begin(),end = hs.end(), ite;

		for (ite = beg; ite != end; ite++)
		{
			if (p == *ite)
			{
				return p;
			}
			return NULL;
		}
			 	
	}

}
           

无环链表的第一个相交节点

#include<iostream>
#include<map>

using namespace std;

typedef struct Node
{
	int data;
	Node* next;
};

typedef struct
{
	Node* head;
	int count;
}Linklist, *pList;

Node* JiaoDian(Node* head1, Node* head2)
{
	if (head1 == NULL || head2 == NULL)
	{
		return NULL;
	}
	int n= 0;
	Node* end1 = head1;
	Node* end2 = head2;
	while (end1->next)
	{
		n++;
		end1 = end1->next;
		
	}
	while (end2->next)
	{
		n--;
		end2 = end2->next;
		
	}
	if (end1 != end2)
	{
		return NULL;
	}
	end1 = n > 0 ? head1 : head2;
	end2 = end1 == head1 ? head2 : head1;
	n = fabs(n);
	while (n != 0)
	{
		end1 = end1->next;
		n--;
	}
	while (end1 != end2)
	{
		end1 = end1->next;
		end2 = end2->next;
	}
		return end1;
}

//哈希表
Node* JiaoDian2(Node* head1, Node* head2)
{
	map<Node*, int> m;
	int n=1;
	while (head1->next)
	{
		m[head1] = n;
		n++;
		head1 = head1->next;
	}
	while (head2->next)
	{
		map<Node*,int>::iterator beg = m.begin(), end = m.end(), ite;
		for (ite = beg; ite != end; ite++)
		{
			if (head2 == ite->first  )
			{
				return head2;
			}
			return NULL;
		}
			 
	}
}
           

分为三种情况 （1）两个有环链表无交点 （2）两个链表有共同的环，与无环链表相交相同（3）有公共环

#include<iostream>
#include <cmath>

using namespace std;

typedef struct Node
{
	int data;
	Node* next;
};

typedef struct
{
	Node* head;
	int count;
}Linklist, *pList;

Node* bothLoop(Node* head1, Node* loop1, Node* head2, Node* loop2)
{
	Node* end1 = NULL;
	Node* end2 = NULL;
	if (loop1 == loop2)
	{
		Node* end1 = head1;
		Node* end2 = head2;
		int n = 0;
		while (end1 != loop1)
		{
			n++;
			end1 = end1->next;
		}
		while (end2 != loop2)
		{
			n--;
			end2 = end2->next;
		}
		end1 = n > 0 ? head1 : head2;
		end2 = end1 == head1 ? head2 : head1;
		n = fabs(n);
		while (n != 0)
		{
			n--;
			end1 = end1->next;
		}
		while (end1 != end2)
		{
			end1 = end1->next;
			end2 = end2->next;
		}
		return end1;
	}
	else
	{
		end1  = loop1->next;
		while (end1 != loop1)
		{
			if (end1 == loop2)
			{
				return loop1;
			}
			end1 = end1->next;
		}
		return NULL;
	}
}