#include <iostream>
using namespace std;

template <class T>
struct Node
{
    T data;
    struct Node<T> *next;
};
template <class T>
class LinkList
{
public:
    LinkList()
    {
        front = new Node<T>;
        front->next = NULL;
    }
    LinkList(T a[], int n);
    ~LinkList();
    void PrintList();
    int GetLength();
    Node<T> *Get(int i);
    T Delete(int i);
    void Insert(int i, T x);
    void Insert1(int i, T x);
    int Locate(T x);
    T middleNode();
    bool checkCycle();

private:
    Node<T> *front;
};

// 带头结点的头插法
template <class T>
LinkList<T>::LinkList(T a[], int n)
{
    Node<T> *front = new Node<T>;
    front->next = NULL;
    for (int i = n - 1; i >= 0; i--)
    {
        Node<T> *tmp = new Node<T>;
        tmp->data = a[i];
        tmp->next = front->next;
        front->next = tmp;
    }
}
// 不带头结点的头插法
template <class T>
LinkList<T>::LinkList(T a[], int n)
{
    if (n == 0)
        return NULL;
    else
        Node<T> *front = new Node<T>;
    front->data = a[n - 1];
    for (int i = n - 2; i >= 0; i--)
    {
        Node<T> *tmp = new Node<T>;
        tmp->next = front;
        tmp->data = a[i];
        front = tmp;
    }
}
// 尾插法
template <class T>
LinkList<T>::LinkList(T a[], int n)
{
    Node<T> *front = new Node<T>;
    front->next = nullptr;
    Node<T> *now = front;
    for (int i = 0; i < n; i++)
    {
        Node<T> *p = new Node<T>;
        p->data = a[i];
        now->next = p;
        now = p;
    }
    now->next = NULL; // 注意
}

template <class T>
LinkList<T>::~LinkList()
{
    Node<T> *p = front;
    while (p)
    {
        front = p;
        p = p->next;
        delete front;
    }
}

template <class T>
int LinkList<T>::GetLength()
{
    Node<T> *p = front->next;
    int len = 1;
    while (p)
    {
        len++;
        p = p->next;
    }
    return len;
}

template <class T>
void LinkList<T>::PrintList()
{
    Node<T> *p = front->next;
    while (p)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}
template <class T>
Node<T> *LinkList<T>::Get(int i)
{
    if (i < 1)
        throw "位置异常";

    Node<T> *p = front->next;
    while (i > 1)
    {
        i--;
        if (p)
        {
            p = p->next;
        }
        else
            throw "溢出";
    }
    return p;
}
// 优化后的
template <class T>
Node<T> *LinkList<T>::Get(int i)
{
    if (i < 1)
        throw "位置异常";
    Node<T> *p = front->next; // 第1个数据结点
    if (!p)
        throw "溢出"; // 空表没有第1个节点
    for (int k = 1; k < i; ++k)
    {
        p = p->next;
        if (!p)
            throw "溢出";
    }
    return p;
}

template <class T>
int LinkList<T>::Locate(T x)
{
    int ans = 0;
    Node<T> *p = front->next;
    while (p)
    {
        ans++;
        if (p->data == x) // 重载
            return ans;
        p = p->next;
    }
    return -1;
}

template <class T>
void LinkList<T>::Insert(int i, T x)
{

    Node<T> *p = front;
    Node<T> *tmp = new Node<T>;
    tmp->data = x;
    int count = 1;
    while (p)
    {
        if (count == i)
        {
            tmp->next = p->next;
            p->next = tmp;
            break;
        }
        count++;
        p = p->next;
    }
    if (p == NULL and count == i) // 这种写法的问题就是如何保证我第i-1个数存在
        throw "位置异常";
    if (count < i || i < 1)
        throw "位置异常";
}
// 使用Get的写法
template <class T>
void LinkList<T>::Insert1(int i, T x)
{
    Node<T> *p = front;
    if (i != 1)
        p = Get(i - 1); // 这里细节一下。如果是1就是更新头结点，为了防止Get函数抛出异常，一定要判断
    if (p)
    {

        Node<T> tmp = new Node<T>;
        tmp->data = x;
        tmp->next = p->next;
        p->next = tmp;
    }
    else
        throw "位置异常";
}
/*
如果 给定某节点p 要求在该节点后插入，那么流程:
new --> new.data --> new->next = p->next --> p->next = new;
对于前插操作流程
只需 交换p 与 new的值

*/
template <class T>
T LinkList<T>::Delete(int i)
{
    Node<T> *p = front;
    if (i != 1)
        p = Get(i - 1);
    p->next = p->next->next;
    T x = del->data;
    delete p;
    return x;
}

template <class T>
T LinkList<T>::middleNode()
{
    Node<T> *p = front;
    Node<T> *q = front;
    while (q)
    {
        p = p->next;
        if (q)
            q = q->next;
        if (q)
            q = q->next;
    }
    return p->data;
}
template <class T>
bool LinkList<T>::checkCycle()
{
    Node<T> *p = front;
    Node<T> *q = front;
    while (q)
    {
        p = p->next;
        if (q)
            q = q->next;
        if (q)
            q = q->next;
        if (p == q)
            return true;
    }
    return false;
}