L142 环形链表 II

未分类

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

解：快慢指针，head->环的起点+环的起点->相遇的点 = 环的长度。

ListNode *detectCycle(ListNode *head) {
        ListNode * fast=head, * slow = head, *cur=head;
        // find meet point
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast) break;
        }
        // if not meet
        if(!fast || !fast->next) return NULL;
        // start from head and meetpoint，fast领先了的一圈，会在入环口第二次相遇
        slow = head;
        while(slow != fast){
            slow = slow->next;
            fast = fast->next;
        }
        return fast;
    }

ListNode *detectCycle(ListNode *head) {
        if(head == NULL) return NULL;
        ListNode * fast = head;
        ListNode * slow = head;
        bool hascycle = false;
        while(fast!=NULL && fast->next!=NULL){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast){
                hascycle = true;
                break;
            }
        }
        if(hascycle){
            slow = head;
            while(slow!=fast){
                slow=slow->next;
                fast = fast->next;
            }
            return slow;
        }
        else return NULL;
    }