[单链表]链表指针追赶问题

前奏

有这样一个问题：在一条左右水平放置的直线轨道上任选两个点，放置两个机器人，请用如下指令系统为机器人设计控制程序，使这两个机器人能够在直线轨道上相遇。（注意两个机器人用你写的同一个程序来控制）。
指令系统：只包含4条指令，向左、向右、条件判定、无条件跳转。其中向左（右）指令每次能控制机器人向左（右）移动一步；条件判定指令能对机器人所在的位置进行条件测试，测试结果是如果对方机器人曾经到过这里就返回true，否则返回false；无条件跳转，类似汇编里面的跳转，可以跳转到任何地方。

ok，这道很有意思的趣味题是去年微软工程院的题，文末将给出解答。同时，我们看到其实这个题是一个典型的追赶问题，那么追赶问题在哪种面试题中比较常见?链表追赶，这篇文章就好好说说在链表中的追赶问题。

环形链表的基本知识

这里说的环形链表是整个链表都是一个环形的，也就是链表的尾结点的next指向了第一个结点。那么看他们的追赶问题。

再看另外的一种情况，就是两个指针的位置不相同。fast在low的前面k的位置：

链表环检测和环入口点检测

上面的分析其实就两个过程：

第一个过程就是链表的环检测，如果两个指针能够相遇，说明一定存在环，否则的话fast指针一定先到末尾的NULL了。

注意：没有中间那个i次移动的结点过程和状态，这里仅仅用于分析问题。

第二个过程就是从链表的碰撞点到链表环的入口结点的距离和从整个链表的第一个结点到链表环的的入口结点的距离是相等的。我们这里没有办法找到这个距离到底是多少，但是可以分别用两个同速度的指针，从两个起始点开始移动，相遇的点就是链表环的入口结点。

ListNode* EntryNodeOfLoop(ListNode* pHead)
{
	if(pHead == NULL)
		return NULL;
	 
	ListNode *low = pHead;
	ListNode *fast = pHead;
	 
	while(fast != NULL && fast->next != NULL)
	{
		low = low->next;
		fast = fast->next->next;
		if(fast == low)
			break;
	}//while
	 
	//no circle return
	if(fast == NULL || fast->next == NULL)
		return NULL;
	 
	low = pHead;
	while(fast != low)
	{
		low = low->next;
		fast = fast->next;
	}//while
	 
	return fast; 
}

计算链表环中结点的个数

首先这个链表要的存在环，如果没有环的话，直接返回0。所以第一步还是链表的环检测，如果两个指针发生了碰撞，那么这个链表存在环。

然后就可以计算环中的结点的个数了，只需要记下来刚才的碰撞点，这个碰撞点一定在环内部，然后在往后遍历，直到再一次的到达这个碰撞点，那么就可以直到环中结点的个数了。

判断两个链表是否相交

问题描述：两个链表的第一个公共结点，如果两个链表不相交的话，返回NULL。

这个问题猛地一看也许看不明白要干什么。其实很简单：

就是求6这个公共结点。

暴力的求解方法：遍历A中的每一个结点，每当遍历到一个结点的时候，都要遍历B中的结点，比较A当前遍历到的结点和B中的哪个结点是相同的。那么这个相同的结点就是第一个公共结点。但是暴力法的时间复杂度是O(m*n)。

可以看到，如果这个公共结点是存在的话，那么这个公共结点之后的结点都是相同的，所以可以从后往前遍历，找最后一个公共结点。

但是单链表是不能从后向前遍历的，所以可以利用栈，把整个链表的各个结点依次装入到栈中，然后依次比较两个栈的栈顶指针。这样就能找到最后一个公共结点。

但是这样的时间复杂度虽然降到了O(m+n)，但是空间复杂度同样的增加到了O(m+n)。还有没有更好的办法呢？答案是有的。

想一想，在暴力算法中，为什么非得用两个嵌套的循环，不能用两个单独的循环，对应位置比对。因为两个链表的长度可能不相等。所以可以通过下面的方法解决：

让长的链表的头指针向后移动，把两个链表弄成一般长。然后依次对比两个链表的结点，就能找到第一个公共结点了。

ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) 
{
	int len1 = GetListLength(pHead1);
	int len2 = GetListLength(pHead2);
	
	int lenDiff = len1 - len2;
	
	ListNode *pListLong = lenDiff > 0 ? pHead1 : pHead2;
	ListNode *pListShort = lenDiff > 0 ? pHead2 : pHead1;
	
	for(int i = 0; i < abs(lenDiff); i++)
	{
		pListLong = pListLong->next;
	}
	
	while(pListLong != NULL && pListShort != NULL && pListLong != pListShort)
	{
		pListLong = pListLong->next;
		pListShort = pListShort->next;
	}
	
	if(pListLong == NULL || pListShort == NULL)
	{
		return NULL;
	}
	else
	{
		return pListLong;
	}
	
}//FindFirstCommonNode()

int GetListLength(ListNode *head)
{
	int length = 0;
	while(head)
	{
		++length;
		head = head->next;
	}//while
	
	return length;
}//GetListLength

但是问题来了，如果两个链表中有环的话，你还能像上面那样，很容易的求解链表的长度吗？

所以要考虑以下的情况：

1.先判断带不带环。
2.如果都不带环，那么就用上面的方法求解第一个公共结点。
3.如果都带环，判断一链表上俩指针相遇的那个节点，在不在另一条链表上。如果在，则相交；如果不在，则不相交。
4.如果一个带环，一个不带环，那么这两个链表一定不相交，没有公共结点。

参考文献地址：

http://blog.csdn.net/v_july_v/article/details/6447013
http://blog.csdn.net/insistgogo/article/details/7584240