#include <iostream>
#include <memory>
#include <vector>

using namespace std;

struct Node {
    int value;
    shared_ptr<Node> next;
    explicit Node(int value) : value(value) {}
};

/**
 * 构建单向链表
 * @return
 */
decltype(auto) build() {
    auto head = make_shared<Node>(100);
    auto temp = head;
    for (int i = 0; i < 10; ++i) {
        temp->next = make_shared<Node>(i);
        temp = temp->next;
    }
    return head;
}

/**
 * 构建交叉链表
 * @return
 */
decltype(auto) build_intersect() {
    auto one = build();
    auto two = build();
    two->next->next->next->next = one->next->next->next;
    return make_pair(one, two);
}

/**
 * 构建循环链表
 * @return
 */
decltype(auto) build_loop() {
    auto one = build();
    auto tail = one;
    auto get = [](int n, shared_ptr<Node> node) -> shared_ptr<Node> {
        for (int i = 1; i < n && node != nullptr; i++) {
            node = node->next;
        }
        return node;
    };
    while (tail->next != nullptr)tail = tail->next;
    tail->next = get(4, one);
    return one;
}

/**
 * 递归逆序
 * @param node
 * @return
 */
shared_ptr<Node> reverse_recursive(shared_ptr<Node> node) {
    if (node->next != nullptr) {
        shared_ptr<Node> head = reverse_recursive(node->next);
        node->next->next = node;
        node->next = nullptr;
        return head;
    }
    return node;
}

/**
 * 递归逆序
 * @param node
 * @return
 */
shared_ptr<Node> reverse(shared_ptr<Node> node) {
    shared_ptr<Node> head = nullptr;
    auto temp = node->next;
    while (temp != nullptr) {
        node->next = head;
        head = node;
        node = temp;
        temp = temp->next;
    }
    node->next = head;
    return node;

}

/**
 * 判断两条链表是否相交
 * @param t1
 * @param t2
 * @return
 */
bool intersect(shared_ptr<Node> &t1, shared_ptr<Node> t2) {
    while (t1->next != nullptr)t1 = t1->next;
    while (t2->next != nullptr)t2 = t2->next;
    return t1 == t2;
}

/**
 * 判断是否是循环链表
 * @param t 头
 * @return  <是否是循环链表, 相遇点>
 */
pair<bool, shared_ptr<Node>> has_loop(const shared_ptr<Node> &t) {
    auto t1 = t->next;
    auto t2 = t->next->next;
    while (t1 != nullptr && t2 != nullptr && t1 != t2) {
        t1 = t1->next;
        t2 = t2->next->next;
    }
    return make_pair(t1 == t2, t1);
}

/**
 * 获取环入口
 * @param h 头
 * @param t 相交点
 * @return
 */
decltype(auto) get_loop_node(const shared_ptr<Node> &h, const shared_ptr<Node> &t) {
    auto x = h, y = t;
    while (x != y) {
        x = x->next;
        y = y->next;
    }
    return x;
}

void print(shared_ptr<Node> node) {
    while (node != nullptr) {
        cout << node->value << " ";
        node = node->next;
    }
    cout << endl;
}


int main() {
    auto common = build();
    print(common);

    auto head = build_loop();
    auto result = has_loop(head);
    if (result.first) {
        cout << result.second->value << endl;
        cout << get_loop_node(head, result.second)->value << endl;
    }
    return 0;
}