Day2-线性表-链表求环的起点

//
// Created by renyi on 2019/5/30.
//
#include<iostream>
using namespace std;

struct Node{
    int value;
    Node* next;
    Node(int v):value(v),next(NULL){}
};

Node* findCycleMeet(Node* head){
    Node* fast = head;//初始化快、慢指针
    Node* slow = head;
    Node* meet = NULL;//初始化指向相遇节点的指针

    while (fast){
        slow = slow->next;//快慢指针先各走一步
        fast = fast->next;
        if (!fast){
            return NULL;//如果fast遇到了链表尾，则说明已遍历完，没相遇，即无环，返回null
        }
        fast = fast->next;//fast再走一步
        if (fast == slow){
            meet = fast;//记录相遇节点
            break;
        }
    }

    while (head && meet){
        if (head == meet){//当head与meet相遇，则说明遍历到了环起点
            return head;
        }
        head = head->next;//head和meet各走一步
        meet = meet->next;
    }
}

int main(){
    Node a(1);
    Node b(2);
    Node c(3);
    Node d(4);
    Node e(5);
    Node f(6);
    Node g(7);

    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    e.next = &f;
    f.next = &g;
    g.next = &d;

    Node* node = findCycleMeet(&a);
    if (node){
        printf("have cycle,and the start node is:%d\n", node->value);
    } else{
        printf("not have cycle");
    }

    return 0;
}