[算法天地]关于单链表的操作有环无环判断

#include <stdio.h>
#include <stdlib.h>

// 有环链表的各种函数测试
typedef struct Node
{
	int data;
	struct Node *next;
}Node;

typedef struct Node* LinkList;

/*链表初始化*/
int InitList(LinkList *L)
{
	*L = (LinkList)malloc(sizeof(Node));
	if(!(*L))
		return -1;
	(*L)->next = NULL;
	return 0;
}

/*求链表的长度*/
int ListLength(LinkList L)
{
	int i = 0;
	LinkList p = L->next;
	while(p)
	{
		i++;
		p = p->next;
	}
	return i;
}

int CreateListHead(LinkList *L, int n)
{
	LinkList p;
	int i;
	for(i=0; i<n; i++)
	{
		p = (LinkList)malloc(sizeof(Node));
		p->data = i+1;
		p->next = (*L)->next;
		(*L)->next = p;
	}
}
	
int CreateListTail(LinkList *L, int n)
{
	LinkList p, r;
	int i;
	r = *L;
	for(i=0; i<n; i++)
	{
		p = (LinkList)malloc(sizeof(Node));
		p->data = i+1;
		r->next = p;
		r = p;
	}
	r->next = NULL;
}

/*打印链表*/
void ListTraverse(LinkList L)
{
	LinkList p = L->next;
	while(p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

/*单链表反转*/
LinkList ListReverse(LinkList L)
{
	LinkList current, pnext, prev;
	if(L == NULL || L->next == NULL)
		return L;
	current = L->next;
	pnext   = current->next;
	current->next = NULL;
	while(pnext)
	{
		prev = pnext->next;
		pnext->next = current;
		current = pnext;
		pnext = prev;
	}
	
	L->next = current;
	return L;
}

LinkList ListReverse2(LinkList L)
{
	LinkList current, p;
	if(L == NULL)
		return NULL;
	current = L->next;
	printf("current = %d\n", current->data);
	while(current->next != NULL)
	{	
		/**举个例子
		*  p = current->next;       // 9个数的话调换需要八次，第一次P等于8
		*  currnet->next = p->next; // P的下一个值7，付给current的下一个
		*  p->next = L->next;       // 把L的第一个节点9赋值给P的下一个值
		*  L->next = p;             // L的下一个值为8，因为上一步P的下一个已经为9
		*/
		p = current->next;          
		current->next = p->next;
		p->next = L->next;
		L->next = p;
	}
	return L;
}



int ListInsert(LinkList *L, int pos, int num)
{
	int j;
	LinkList p, s;
	p = *L;
	j = 1;
	while(p && j<pos)
	{
		p = p->next;
		++j;
	}
	
	if( !p || j>pos )
		return -1;
	
	s = (LinkList)malloc(sizeof(Node));
	s->data = num;
	s->next = p->next;
	p->next = s;
	return 0;
}

int IsEmpty(LinkList L)
{
	if(L->next)
		return -1;
	else
		return 1;
}

int BuildListLoop(LinkList *L, int num)
{
	int i = 0;
	LinkList cur = (*L)->next;
	LinkList tail= NULL;
	
	if(num <= 0 || L == NULL)
		return -1;
	
	for(i=1; i<num; ++i)
	{
		if(cur == NULL)
		{
			return -1;
		}
		cur = cur->next;
	}
	tail = cur;
	while(tail->next)
	{
		tail = tail->next;
	}
	tail->next = cur;
	return 0;
	
}

int ListTraveseLimit(LinkList L, int n)
{
	int i = 0;
	LinkList p = L->next;
	while(p && i<n)
	{
		printf("%d ", p->data);
		p = p->next;
		i++;
	}
	printf("\n只显示%d个\n", n);
	return 0;
}

int HasLoop(LinkList L)
{
	LinkList fast = L;
	LinkList slow = L;
	
	/** 
	* 这里如果无环，则fast先到达终点
	* 当链表长度为奇数时，fast->next为空  
	* 当链表长度为偶数时，fast为空
	*/
	
	while( fast != NULL && fast->next != NULL )
	{
		fast = fast->next->next;
		slow = slow->next;
		if( fast == slow )
			break;
	}
	
	if( fast == NULL || fast->next == NULL )
		return -1;
	else
		return 1;
}

int LoopLength(LinkList L)
{
	if(-1 == HasLoop(L))
		return 0;
	
	LinkList fast = L;
	LinkList slow = L;
	
	int length = 0;
	bool begin = false;
	bool again = false;
	
	while( fast != NULL && fast->next != NULL )
	{
		fast = fast->next->next;
		slow = slow->next;
		
		// 超两圈后停止计数，跳出循环
		if( fast == slow && again == true )
		{
			break;
		}
		
		// 超一圈后开始计数
		if( fast == slow && again == false )
		{
			begin = true;
			again = true;
		}
		
		// 计数
		if( begin == true )
			++length;
	}
	return length;
}

// 解决入口点的问题思路
//              8 O-O 7
//               /   //            9 O     O 6
//               \   /
// O - O - O - O - O
// 1   2   3   4   5
// 相遇点到连接点的距离等于头指针到连接点的距离
// 先让快慢指针相遇，然后慢指针重新指向头结点
// 分别从相遇点、头指针开始走，相遇的那个店就是连接点
LinkList findLoopEnterace(LinkList L)
{
	LinkList fast = L;
	LinkList slow = L;
	
	while( fast != NULL && fast->next != NULL )
	{
		fast = fast->next->next;
		slow = slow->next;
		
		// 如果有环，则fast会超过slow一圈
		if(fast == slow)
			break;
	}
	
	if(fast == NULL || fast->next == NULL)
		return NULL;
	
	slow = L;
	while(slow != fast)
	{
		slow = slow->next;
		fast = fast->next;
	}
	
	return slow;
}

int GetMidNode(LinkList L, int *e)
{
	LinkList fast = L;
	LinkList slow = L;
	
	while( fast->next != NULL )
	{
		if( fast->next->next != NULL )
		{
			fast = fast->next->next;
			slow = slow->next;
		}
		else
		{
			fast = fast->next;
		}
	}
	
	*e = slow->data;
	return 0;
	
}

int ClearList(LinkList *L)
{
	LinkList p, q;
	p = (*L)->next;
	while(p)
	{
		q = p->next;
		free(p);
		p = q;
	}
	(*L)->next = NULL;
	return 0;
}

int main()
{
	LinkList L;
	int i;
	int n;
	int e;
	
	i = InitList(&L);
	if(i != -1)
		printf("InitList() 初始化成功.\n");
	
	printf("链表L初始化后, ListLength(L)=%d\n", ListLength(L));
	
	for(i=0; i<10; i++)
	{
		ListInsert(&L, 1, i);
	}
	printf("IsEmpty = %d(1:空，-1：非空)\n", IsEmpty(L));
	printf("ListLength(L)=%d\n", ListLength(L));
	printf("打印链表：");
	ListTraverse(L);
	
	// 给单链表逆向反转
	ListReverse2(L);
	printf("逆向打印链表：");
	ListTraverse(L);
	
	// 求链表的中间节点
	GetMidNode(L, &e);
	printf("求链表的中间节点e=%d\n", e);
	
	printf("给链表建环, 请输入位置:");
	scanf("%d", &n);
	BuildListLoop(&L, n);
	ListTraveseLimit(L, 20);
	
	// 判断链表是否有环
	if( 1 == HasLoop(L) )
		printf("链表有环\n");
	else
		printf("链表无环\n");
	
	// 计算环长
	printf("计算环长, LoopLength(L)=%d\n", LoopLength(L));
	
	// 求出环的入口点
	LinkList enterance = findLoopEnterace(L);
	printf("入口点的值为: %d\n", enterance->data);
	
	//printf("采用头插法：\n", CreateListHead(&L, 10));
	//ListTraverse(L);
	
	//printf("采用尾插法\n", CreateListTail(&L, 10));
	//ListTraverse(L);
	
	//i = ClearList(&L);
	//if( i == 0 )
	//	printf("清空LinkList链表.\n");
	//printf("IsEmpty = %d(1:空，-1：非空)\n", IsEmpty(L));
	//printf("ListLength(L)=%d\n", ListLength(L));
	

	return 0;
}