博客

问题1：怎样才能检测到链表中存在循环？

书中给出的最终算法是定义两个指针p1,p2，p1每次移动一个位置，而p2每次移动两个位置，这样如果链表中存在循环，那么p2一定能追上p1。如果不存在，那么p2会到达链表尾部，即检测到空

//这个算法，并没有找到入口，而是找到了相遇点
bool hasCircle(Node* head, Node* &encounter)  
{  
    Node *fast = head, *slow = head;  
    while(fast && fast->next)  
    {  
        fast = fast->next->next;  
        slow = slow->next;  
        if(fast == slow)  
        {  
            encounter = fast;  
            return true;  
        }  
    }  
    encounter = NULL;  
    return false;  
}  

问题2：有一个单链表，其中可能有一个环，也就是某个节点的next指向的是链表中在它之前的节点，这样在链表的尾部形成一环。如果链表存在环，找到环的入口点？

第一种解法：

需要辅助空间，可以用散列表，用来存放结点的地址。（用散列表为O(n)，而用集合为O(nlogn)，而空间复杂度为O(n)）

//运用集合set，没找到就插入，找到了，就是第二次相遇
//函数功能 ： 找含单链表的环入口点  
//函数参数 ： pHead指向链表首部  
//返回值 ：   返回的是环的入口点，如果不存在环，返回NULL  
ListNode* FindFirstCrossNode_Solution1(ListNode * pHead)  
{  
    set<ListNode *> addrSet; //这里用集合代替散列，会影响时间复杂度   
    ListNode *pNode = pHead;  
    while(pNode != NULL)  
    {  
        if(addrSet.find(pNode) == addrSet.end())  
            addrSet.insert(pNode);  
        else  
            break;  
        pNode = pNode->next;  
    }  
    return pNode;  
} 

第二种解法：

容易想到的就是用穷举法，对于每个结点，检查该结点是否是环的入口点。

这种方法先让外循环走到相交点，内循环走到这个点，点相等距离不一样所以就是它。

ListNode* FindFirstCrossNode_Solution2(ListNode * pHead)  
{  
    ListNode *p1 = pHead;  
    int pos1 = 0;  
    while(p1)   //检查链表的每个结点  
    {  
        ListNode *p2 = pHead;  
        int pos2 = 0;  
        while(p2) //每次都从头开始  
        {  
            if(p1 == p2) //两个指针指向的结点一样，可能是相交也可能不相交  
            {  
                if(pos1 == pos2) //两个指针走过的距离一样  
                    break;  
                else  //p1在环中绕了一圈，导致pos1与pos2不一样  
                    return p1;   
            }  
            p2 = p2->next; //前进一个位置  
            pos2++;        //记录走过的距离  
        }  
        p1 = p1->next;  
        pos1++;  
    }  
    return NULL;  
}

最聪明，却又最简单的解法！！！

借用问题1找到的相遇点；相遇点到环入口，跟从Head开头到环入口，是一样的距离。（因为p2走的距离是p1的两倍，多走的是一部分圆和这个小尾巴）

Node* findEntry(Node* head, Node* encounter)  
{   
    Node *p1 = head, *p2 = encounter;  
    while(p1 != p2)  
    {  
        p1 = p1->next;  
        p2 = p2->next;  
    }  
    return p1;  
}