// CircularLinkList1.h
#pragma once
struct Node
{
    Node(int value) : data(value) {}
    int data;
    Node* next = nullptr;
};

// 单向循环链表
class LoopLinkList1
{
public:
    LoopLinkList1();
    ~LoopLinkList1();

    // 判断链表是否为空
    bool isEmpty();
    // 得到链表长度
    int length();
    // 数据添加到链表头部
    void prepend(int data);
    // 数据添加到链表尾部
    void append(int data);
    // 数据插入到链表任意位置, 第一个数据元素 pos=1
    bool insert(int pos, int data);
    // 搜索数值, 返回节点和位置, 没找到返回nullptr
    Node* find(int data, int& pos);
    // 删除节点
    bool remove(int pos);
    // 遍历链表
    void display();

private:
    Node* m_head = nullptr;
    Node* m_tail = nullptr;
    int m_length = 0;
};

// CircularLinkList1.cpp
#include "CircularLinkList1.h"
#include <iostream>
using namespace std;

LoopLinkList1::LoopLinkList1()
{
}

LoopLinkList1::~LoopLinkList1()
{
    while (!isEmpty())
    {
        remove(1);
    }
}

bool LoopLinkList1::isEmpty()
{
    return m_head == nullptr && m_tail == nullptr;
}

int LoopLinkList1::length()
{
    return m_length;
}

void LoopLinkList1::prepend(int data)
{
    Node* node = new Node(data);
    if (m_head == nullptr)
    {
        m_head = m_tail = node;
    }
    else
    {
        node->next = m_head;
        m_head = node;
    }
    m_tail->next = m_head;
    m_length++;
}

void LoopLinkList1::append(int data)
{
    Node* node = new Node(data);
    if (m_head == nullptr)
    {
        m_head = m_tail = node;
    }
    else
    {
        m_tail->next = node;
        m_tail = node;
    }
    m_tail->next = m_head;
    m_length++;
}

bool LoopLinkList1::insert(int pos, int data)
{
    if (pos<1 || pos>length() + 1)
    {
        cout << "插入数据 " << data << " 失败, 无效位置" << endl;
        return false;
    }
    Node* pNode = new Node(data);
    if (m_head == nullptr)
    {
        m_head = m_tail = pNode;
        m_tail->next = m_head;
        m_length++;
        return true;
    }
    if (pos == 1)
    {
        pNode->next = m_head;
        m_head = pNode;
        m_tail->next = m_head;
    }
    else
    {
        Node* p = m_head;
        int j = 1;
        while (j < pos - 1 && p != nullptr)
        {
            p = p->next;
            j++;
        }
        pNode->next = p->next;
        p->next = pNode;
        if (pos == length() + 1)
        {
            m_tail = pNode;
        }
    }
    m_length++;
    return true;
}

Node* LoopLinkList1::find(int data, int& pos)
{
    pos = 1;
    Node* p = m_head;
    do
    {
        if (p->data == data)
        {
            return p;
        }
        p = p->next;
        pos++;
    } while (p != m_head);
    return nullptr;
}

bool LoopLinkList1::remove(int pos)
{
    if (pos<1 || pos>length())
    {
        cout << "删除失败, 无效的pos位置" << endl;
        return false;
    }
    Node* p = m_head;
    for (int i = 1; i < pos - 1; ++i)
    {
        p = p->next;
    }
    if (pos == 1)
    {
        if (p->next == m_head)
        {
            delete m_head;
            m_head = m_tail = nullptr;
        }
        else
        {
            m_head = m_head->next;
            m_tail->next = m_head;
            delete p;
        }
    }
    else
    {
        Node* delNode = p->next;
        p->next = delNode->next;
        delete delNode;
        if (pos == m_length)
        {
            m_tail = p;
        }
    }
    m_length--;
    return true;
}

void LoopLinkList1::display()
{
    if (m_head == nullptr)
    {
        cout << "空链表" << endl;
        return;
    }
    Node* p = m_head;
    cout << "遍历链表: ";
    do {
        cout << p->data << " ";
        p = p->next;
    } while (p != m_head);
    cout << endl;
}

int main()
{
    LoopLinkList1 lst;
    lst.insert(1, 12);
    lst.append(8);
    lst.insert(2, 7);
    lst.insert(2, 6);
    lst.insert(1, 5);
    lst.insert(2, 4);
    lst.append(3);
    lst.prepend(9);
    lst.display();
    cout << "当前链表的长度为: " << lst.length() << endl;
    cout << "========== 测试搜索和删除=========" << endl;
    LoopLinkList1 lst1;
    lst1.append(10);
    lst1.append(20);
    lst1.append(30);
    lst1.append(40);
    lst1.append(50);
    lst1.display();
    int pos;
    Node* node = lst1.find(10, pos);
    cout << "搜索到的节点位置: " << pos << ", 值为: " << node->data << endl;
    lst1.remove(pos);
    lst1.display();

    node = lst1.find(30, pos);
    cout << "搜索到的节点位置: " << pos << ", 值为: " << node->data << endl;
    lst1.remove(pos);
    lst1.display();

    node = lst1.find(50, pos);
    cout << "搜索到的节点位置: " << pos << ", 值为: " << node->data << endl;
    lst1.remove(pos);
    lst1.display();
    cout << "当前链表的长度为: " << lst1.length() << endl;

    return 0;
}

遍历链表: 9 5 4 12 6 7 8 3
当前链表的长度为: 8
========== 测试搜索和删除=========
遍历链表: 10 20 30 40 50
搜索到的节点位置: 1, 值为: 10
遍历链表: 20 30 40 50
搜索到的节点位置: 2, 值为: 30
遍历链表: 20 40 50
搜索到的节点位置: 3, 值为: 50
遍历链表: 20 40
当前链表的长度为: 2