142. Linked List Cycle II

まず141.Linked List Cycle . Given a linked list, determine if it has a cycle in it. チェーンテーブルにリングがあるかどうかを判断し、2つのスローポインタで移動して重なるかどうかを確認すればいい.

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *first=head,*sec=head;
        while(first!=NULL&&sec!=NULL&&sec->next!=NULL){
            first=first->next;
            sec=sec->next->next;
            if(first==sec)
                return true;
        }
        return false;
    }
};

問題142は,ループがあるか否かを判断するだけでなく,ループの入口接点を求める必要がある.余分なスペースの使用が許可されている場合.

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        map<ListNode*,bool>;
        while(head!=NULL){
            if(v[head]==true)
                return head;
            v[head]=true;
            head=head->next;
        }
        return NULL;
    }
};

余分なスペースがなければ、同じように2つのポインタが必要です.スナップポインタが出会うと、スナップポインタをヘッドノードに設定し、スナップポインタが一歩前進するたびに、出会うとリングの入り口になります.

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *first=head,*sec=head;
        int fla=1;
        while(first!=NULL&&sec!=NULL&&sec->next!=NULL){
            first=first->next;
            sec=sec->next->next;
            if(first==sec){
                fla=0;
                break;
            }
        }
        if(fla)
            return NULL;
        sec=head;
        while(sec!=NULL&&first!=NULL){
            if(sec==first)break;
            sec=sec->next;
            first=first->next;
        }
        return first;
    }

};