学步园

单向链表的长度定义为链表中的节点个数。如果链表中没有环则用如下算法

链表节点定义如下

struct node
{
	int v;
	node *next;
};

算法如下

/*
返回链表的长度
链表为空 返回0
*/
size_t listLen(node * p)
{
	size_t num = 0;
	while (p!=NULL)
	{
		num++;
		p = p->next;
	}
	return num;
}

由于有环的存在，因此上面的算法有可能陷入死循环。

对于链表有没有环，可设置两个指针，访问链表。一个前进的快点，一个慢点。如果有环，那么两个指针必将相遇。因此判断链表有没有环算法如下：

bool haveRing(node *p)
{
	node * slow = p; // 遍历的慢 每次前进一个节点
	node * fast = p; // 遍历的快，每次前进二个节点
	if(fast != NULL)
	{
		fast = fast ->next; //让fast先走一步
	}
	while (fast&& fast->next)
	{
		if (fast == slow || fast->next == slow)
		{
			break;
		}
		slow = slow->next;
		fast = fast->next->next;
	}
	return !(fast == NULL || fast->next == NULL);
}

当有环的时候如何求环的入口节点呢？

设环的长度为r,链表长度为L,节点相遇时slow走了s步，fast在环中转了n圈，入口环与相遇点距离为x，起点到环入口点的距离为a。slow走一步，fast走两步。

因此

1. 2s=nr+s
2. s= nr
4. s = a + x
5. L = a + r    =>   r = L - a
6.  
7. a+x  = nr 
8. = (n-1)r + r 
9. = (n-1)r + L -a
10.  
11. a = (n-1)r + L -a - x
12. a = (n-1)r + L-s

L-s为从相遇点开始到环入口的距离。公式12就是说也就是说，从相遇点开始，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。

算法如下：

/*
返回链表的结尾
如果没有环，则返回NULL
如果有环，则返回节点的next 为环的入口节点
*/
node * FindListTail(node *p)
{   
	node * slow = p; // 遍历的慢 每次前进一个节点
	node * fast = p; // 遍历的快，每次前进二个节点
	if(fast != NULL)
	{
		fast = fast ->next; //让fast先走一步
	}
	while (fast&& fast->next)
	{
		if (fast == slow || fast->next == slow)
		{
			break;
		}
		slow = slow->next;
		fast = fast->next->next;
	}
	//没有环
	if (fast == NULL || fast->next == NULL)
	{
		return NULL;
	}
	//slow表示相遇节点
	if (fast->next == slow)
	{
		slow = fast ->next;
	}
	fast = p; // 现在fast每次也仅前进一步
	node *tail = NULL;
	while (slow != fast)
	{
		tail = slow;
		slow = slow->next;
		fast = fast->next;
	}
	return tail; 
}

最后，求链表的长度算法如下：

size_t listLen(node * p)
{
	node * tail = FindListTail(p);
	size_t num = 0;
	while (p!=tail)
	{
		num++;
		p = p->next;
	}
	if (tail != NULL)
	{
		num +=1; // 加上最后一个节点
	}
	return num;
}

参考http://blog.csdn.net/lock0812/article/details/2644109