[資料結構] 單連結清單如何判環以及求環的長度,入口

目錄

​​如何判環?​​

​​如何求環的長度?​​

​​如何求環的入口呢?​​

​​示例​​

如何判環?

思路: 利用兩個移動速度不同的指針,若在均不為空的情況下相遇,則存在環

如何求環的長度?

思路:若存在環,那麼快慢指針從相遇點重新出發到再次相遇的過程中, 一定是慢指針走了一圈，快指針走了兩圈, 慢指針所走過的步數即為環的長度

如何求環的入口呢?

推理:

 是以,我們在相遇點位和連結清單的起點分别設立兩個速度相同的指針,當他們相遇時即在環的入口

示例

其中測試資料的關系如圖

#include<iostream>
using namespace std;

typedef struct SingleListNode{
    int value;
    SingleListNode* next;
    SingleListNode(int v):value(v),next(NULL){}
}SLNode;

class SingleList{
    public:
        SLNode* phead;
        SingleList();
        bool isCircle(){
            return firstMeet(phead) != NULL;
        }
        int getCircleLenth();
        int getCircleEntrance();
        void headInsert(int value);

    private:
        
        SLNode* firstMeet(SLNode* phead);

};

SingleList::SingleList()
{
    phead = new SLNode(0);
}

void SingleList::headInsert(int value)
{
    SLNode* newNode = new SLNode(value);
    newNode->next = phead->next;
    phead->next = newNode;
}

SLNode* SingleList::firstMeet(SLNode* phead)
{
    SLNode* pslow, *pfast;
    pslow = pfast = phead->next;

    while(pslow && pfast)       //若存在環的話兩個工作指針必不會出現空的情況
    {
        pslow = pslow->next;
        pfast = pfast->next ? pfast->next->next : pfast->next;

        if(pslow->value == pfast->value) return pslow;
    }
    return NULL;       
}

int SingleList::getCircleLenth()
{
    SLNode* pfirstMeet = firstMeet(phead);
    
    //無環的情況
    if(!pfirstMeet) return 0;

    SLNode* pslow, *pfast;
    pslow = pfast = pfirstMeet;
    int step = 0;
    while(pslow && pfast)
    {
        pslow = pslow->next;
        step ++;
        pfast = pfast->next ? pfast->next->next : pfast->next;
        if(pslow->value == pfast->value) return step;
    }
}

int SingleList::getCircleEntrance()
{
    SLNode* pfirstMeet = firstMeet(phead);
    
    //無環的情況
    if(!pfirstMeet) return -1;

    SLNode* p1 = phead->next;
    SLNode* p2 = pfirstMeet;

    while(p1 != p2)
    {
        p1 = p1->next;
        p2 = p2->next;
    }
    return p1->value;
}

int main()
{
    SingleList* list = new SingleList();
    
    SLNode* p1 = new SLNode(1);
    SLNode* p3 = new SLNode(3);
    SLNode* p5 = new SLNode(5);
    SLNode* p7 = new SLNode(7);
    SLNode* p2 = new SLNode(2);
    SLNode* p4 = new SLNode(4);

    p1->next = p3;
    p3->next = p5;
    p5->next = p7;
    p7->next = p2;
    p2->next = p4;
    p4->next = p5;
    list->phead->next = p1;
    
    if(list->isCircle()){
        cout << "存在環,且長度為: " << list->getCircleLenth() <<  endl; 
        cout << "環的入口為: " << list->getCircleEntrance(); 
    }else{
        cout << "不存在環" ; 
    }

    return 0;
}      

輸出: