判断两个单项链表是否相交（有公共节点），这两个链表可以有环。

大体流程分两部分：
第一部分——判断单个链表是否有环
使用两个指针，一个快指针，一个慢指针，快指针一次走两步，慢指针一次走一步；
若快指针最后变为空，则单链表为无环单链表，返回空指针；
若快慢指针在某一时刻指向同一节点，即二者完全一样，则为有环单链表，
此时让快指针重新指向链表头结点，然后快慢指针均一次走一步，
当快慢指针再次相同时，则此节点即为链表入环节点，将其返回。
第二部分——判断链表是否相交
情况一：两链表中一个为有环链表，一个为无环链表，则此时两链表一定不相交，返回空即可；
情况二：两个链表都是无环链表，此时有两种情况，1）两个无环链表相交；2）两个无环链表不相交；
首先遍历两链表，分别得到两个链表的长度，
取两个长度的差值，然后让长链表先遍历差值长度，此时长链表剩余部分与短链表长度相同，
然后两条链表同时遍历，直到遇到相同节点为止，若相同节点为空，则两链表不相交，返回空，
否则两链表相交，返回相交节点即可；
情况三：两个链表都是有环链表，此时有三种情况，1）两个有环链表不相交；2）两个有环链表相交，且交点在环外；3）两个有环链表相交，且交点在环内。
首先获得两个链表的入环节点，若入环节点相同，则可转变为情况二，此时将入环节点作为链表的终止节点即可；若两个入环节点不同，以一个入环节点开始遍历，若遍历一遍过程中都没有遇见另一个入环节点，则两链表不相交，返回空，若遇到另一入环节点，则说明两链表相交，此时返回任意一个入环节点即可。

借用层主 BugBug快走开 的思路，我用代码将其实现，并提供测试用例：

大体流程分两部分：
第一部分——判断单个链表是否有环
使用两个指针，一个快指针，一个慢指针，快指针一次走两步，慢指针一次走一步；
若快指针最后变为空，则单链表为无环单链表，返回空指针；
若快慢指针在某一时刻指向同一节点，即二者完全一样，则为有环单链表，
此时让快指针重新指向链表头结点，然后快慢指针均一次走一步，
当快慢指针再次相同时，则此节点即为链表入环节点，将其返回。
第二部分——判断链表是否相交
情况一：两链表中一个为有环链表，一个为无环链表，则此时两链表一定不相交，返回空即可；
情况二：两个链表都是无环链表，此时有两种情况，1）两个无环链表相交；2）两个无环链表不相交；
首先遍历两链表，分别得到两个链表的长度，
取两个长度的差值，然后让长链表先遍历差值长度，此时长链表剩余部分与短链表长度相同，
然后两条链表同时遍历，直到遇到相同节点为止，若相同节点为空，则两链表不相交，返回空，
否则两链表相交，返回相交节点即可；
情况三：两个链表都是有环链表，此时有三种情况，1）两个有环链表不相交；2）两个有环链表相交，且交点在环外；3）两个有环链表相交，且交点在环内。
首先获得两个链表的入环节点，若入环节点相同，则可转变为情况二，此时将入环节点作为链表的终止节点即可；若两个入环节点不同，以一个入环节点开始遍历，若遍历一遍过程中都没有遇见另一个入环节点，则两链表不相交，返回空，若遇到另一入环节点，则说明两链表相交，此时返回任意一个入环节点即可。

#include<iostream>

using namespace std;

struct ListNode {
      int val;
      struct ListNode *next;
      ListNode(int x) :
            val(x), next(NULL) {
      }
};

class Solution {
public:
	//判断两个单向链表是否相交，若相交返回相交节点，不相交则返回空
	ListNode* getIntersectNode(ListNode* head1, ListNode* head2)
	{
		ListNode* loop1 = findLoop(head1);
		ListNode* loop2 = findLoop(head2);
		// (1)两个无环链表的相交问题
		if (loop1 == NULL && loop2 == NULL)
		{
			return noLoop(head1, head2);
		}
		// (2)一个链表有环，一个链表无环，不可能相交
		else if (loop1 == NULL || loop2 == NULL)
		{
			return NULL;
		}
		// (3)两个有环链表相交问题
		else
		{
			return bothLoop(head1, loop1, head2, loop2);
		}
	}
private:
	//(1)判断链表是否有环，若有返回入环节点，若没有返回空
	ListNode* findLoop(ListNode* head)
	{
		ListNode* slow = head;
		ListNode* fast = head;
		bool flag = false; //标志位，记录是否有环
		while (fast->next && fast->next->next)
		{
			slow = slow->next;
			fast = fast->next->next;
			if (slow == fast) //快指针追上慢指针则有环
			{
				flag = true;
				break;
			}
		}
		if (flag) //有环返回入环节点
		{
			fast = head;
			while (fast != slow)
			{
				fast = fast->next;
				slow = slow->next;
			}
			return fast;
		}
		else //无环返回空
		{
			return NULL;
		}
	}

	//(2)判断两个无环链表是否相交，若相交返回相交节点，否则返回空
	ListNode* noLoop(ListNode* head1, ListNode* head2)
	{
		ListNode* p1 = head1;
		ListNode* p2 = head2;
		while (p1 != p2)
		{
			p1 = p1 != NULL ? p1->next : head1;
			p2 = p2 != NULL ? p2->next : head2;
		}
		return p1;
	}

	//(3)判断两个有环链表是否相交，若相交返回相交节点，否则返回空
	ListNode* bothLoop(ListNode* head1, ListNode* loop1, ListNode* head2, ListNode* loop2)
	{
		//(3.1)入环节点相同，相交节点可能在环外，也可能就是这个入环节点
		if (loop1 == loop2)
		{
			ListNode* p1 = head1;
			ListNode* p2 = head2;
			while (p1 != p2)
			{
				p1 = p1 != loop1 ? p1->next : head2;
				p2 = p2 != loop2 ? p2->next : head1;
			}
			return p1;
		}
		//(3.2)入环节点不同，可能不想交，也可能相交在环内
		else
		{
			ListNode* cur = loop1->next;
			while (cur != loop1)
			{
				if (cur == loop2) // 相交在环内，返回loop1，或loop2均可
				{
					return loop1;
				}
				cur = cur->next;
			}
			return NULL; // 不相交
		}
	}
};


int main()
{
	Solution* s = new Solution();

	//simple01
	// 1->2->3->4->5->6->7->null
	ListNode* head1 = new ListNode(1);
	head1->next = new ListNode(2);
	head1->next->next = new ListNode(3);
	head1->next->next->next = new ListNode(4);
	head1->next->next->next->next = new ListNode(5);
	head1->next->next->next->next->next = new ListNode(6);
	head1->next->next->next->next->next->next = new ListNode(7);
	// 0->9->8->6->7->null
	ListNode* head2 = new ListNode(0);
	head2->next = new ListNode(9);
	head2->next->next = new ListNode(8);
	head2->next->next->next = head1->next->next->next->next->next; // 8->6
	cout << s->getIntersectNode(head1, head2)->val << endl;


	//simple02
	// 1->2->3->4->5->6->7->4...
	head1 = new ListNode(1);
	head1->next = new ListNode(2);
	head1->next->next = new ListNode(3);
	head1->next->next->next = new ListNode(4);
	head1->next->next->next->next = new ListNode(5);
	head1->next->next->next->next->next = new ListNode(6);
	head1->next->next->next->next->next->next = new ListNode(7);
	head1->next->next->next->next->next->next = head1->next->next->next; // 7->4
																// 0->9->8->2...
	head2 = new ListNode(0);
	head2->next = new ListNode(9);
	head2->next->next = new ListNode(8);
	head2->next->next->next = head1->next; // 8->2
	cout << s->getIntersectNode(head1, head2)->val << endl;


	//simple03
	// 0->9->8->6->4->5->6..
	head2 = new ListNode(0);
	head2->next = new ListNode(9);
	head2->next->next = new ListNode(8);
	head2->next->next->next = head1->next->next->next->next->next; // 8->6
	cout << s->getIntersectNode(head1, head2)->val << endl;

	system("pause");
	return 0;
}