如何判断单链表是否成环以及查找环的接入点

首先定义一个判断工具

typedef unsigned char Boolean;

#define TURE 1
#define FLASE 0

1、是否带环判断：使用追赶的方法，设定两个指针slow、first，从头指针开始，每次分别前进1步、2步。如存在环，则两者相遇；如不存在环，fast遇到NULL退出。

Boolean FindListTail(PList &head, PList &hNode) {
	Boolean OK = FLASE;
    Node *slow, *fast;
    slow = fast = head;
    while(fast != NULL && fast -> next != NULL) {
        fast = fast -> next -> next;
        slow = slow-> next;
        if(fast == slow) {
            hNode = fast;
            OK = TURE;
        }
    }
    return OK;
}

环的接入点：碰撞点p到连接点的距离=头指针到连接点的距离，因此，分别从碰撞点、头指针开始走，相遇的那个点就是连接点。

Node *findLoopPort(PList head) {
	if(head == NULL || head-> next == NULL) 
        return NULL;
    Node *slow,*fast;
    slow = fast = head;
    while(fast != NULL && fast-> next != NULL) {
        fast = fast-> next-> next;
        slow = slow -> next;
        if(fast == slow)
            break;
    }
    if(fast != slow) 
        return NULL;
    fast = head;               
    while(fast != slow) {
        fast = fast -> next;
        slow = slow -> next;
    }
    return fast;
}