单向链表

linked_list.cpp

#include <iostream>
#include <cassert>

template <typename T>
struct Node
{
    T value;
    Node<T> *next;
};

template <typename T>
class LinkedList
{
    Node<T> *head;
    Node<T> *tail; // 当 node->next 为 nullptr 时，说明是尾节点
    int size;

public:
    LinkedList() : head(nullptr), tail(nullptr), size(0) {}

    Node<T> *get_node_by_index(int index) // return node at given index
    {
        if (index < 0 || index >= size)
            return nullptr;
        Node<T> *node = head;
        while (index--)
        {
            if (!node)
                return nullptr;
            node = node->next;
        }
        return node;
    }

    Node<T> *get_node_by_value(T value, int times) // return node with given value occurs times
    {
        Node<T> *node = head;
        int index = 0;
        while (node && times)
        {
            if (node->value == value)
            {
                if (times-- == 1)
                    return node;
            }
            node = node->next;
            index++;
        }
        return nullptr;
    }

    int get_index_by_value(T value, int times) // return index of value occurs times
    {
        Node<T> *node = head;
        int index = 0;
        while (node && times)
        {
            if (node->value == value)
            {
                if (times-- == 1)
                    return index;
            }
            node = node->next;
            index++;
        }
        return -1;
    }

    Node<T> *get_back()
    {
        return tail;
    }

    // 在头部插入需要考虑尾部指针的更新
    void push_front(T value)
    {
        head = new Node<T>{value, head};
        if (!tail)
        {
            tail = head;
        }
        size++;
    }

    // 在尾部插入需要考虑头部指针的更新
    void push_back(T value)
    {
        Node<T> *newNode = new Node<T>{value, nullptr};
        if (!head)
        {
            head = tail = newNode;
            size++;
            return;
        }
        tail->next = newNode;
        tail = newNode;
        size++;
    }

    void insert(int index, T value)
    {
        if (index < 0 || index > size)
            return;
        if (index == 0)
        {
            head = new Node<T>{value, head};
            if (!tail) // 和 push_front 一样的逻辑，更新 tail
            {
                tail = head;
            }
        }
        else if (index == size) // 参考 stl 是 [begin, end) 范围，所以允许 index == size 插入到末尾
        {
            Node<T> *newNode = new Node<T>{value, nullptr};
            if (tail == nullptr)
            {
                head = tail = newNode;
            }
            else
            {
                tail->next = newNode;
                tail = newNode;
            }
        }
        else
        {
            Node<T> *lastNode = get_node_by_index(index - 1);
            Node<T> *newNode = new Node<T>{value, lastNode->next};
            lastNode->next = newNode;
            if (newNode->next == nullptr) // 如果是插入到末尾，更新 tail
            {
                tail = newNode;
            }
        }
        size++;
    }

    void remove_by_index(int index)
    {
        if (index < 0 || index >= size)
            return;
        if (index == 0)
        {
            Node<T> *delNode = head;
            head = head->next;
            if (head == nullptr) // 如果删除后链表为空，更新 tail
            {
                tail = nullptr;
            }
            delete delNode;
            size--;
        }
        else
        {
            Node<T> *lastNode = get_node_by_index(index - 1);
            if (lastNode->next)
            {
                Node<T> *delNode = lastNode->next;
                if (delNode == tail) // 如果删除的是尾节点，更新 tail
                {
                    tail = lastNode;
                }
                lastNode->next = delNode->next;
                delete delNode;
                size--;
            }
        }
    }

    void remove_by_value(T value, int times) // remove node with value
    {
        Node<T> *node = head;
        Node<T> *lastNode = nullptr;
        while (node && times)
        {
            if (node->value == value)
            {
                if (times-- == 1)
                {
                    if (lastNode) // 不是头节点
                    {
                        lastNode->next = node->next;
                    }
                    else // 是头节点
                    {
                        head = node->next;
                    }

                    if (node == tail) // 如果删除的是尾节点，更新 tail
                    {
                        tail = lastNode; // 如果 lastNode 是 nullptr，说明链表变空，tail 也会被置为 nullptr
                    }
                    delete node;
                    size--;
                    return;
                }
            }
            lastNode = node;
            node = node->next;
        }
    }

    void pop()
    {
        remove_by_index(0);
    }

    void display()
    {
        Node<T> *cur = head;
        while (cur)
        {
            std::cout << cur->value << " -> ";
            cur = cur->next;
        }
        std::cout << "NULL\n";
    }

    // 逐个步进反转
    void reverse() {
        if (!head) return;
        Node<T> *old_head = head;
        Node<T> *cur = head;
        Node<T> *prev = nullptr;
        Node<T> *next = nullptr;

        while (cur) {
            next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        head = prev;
        tail = old_head;
    }

    // 这个递归会始终返回原链表的最后一个元素
    // 然后在返回前，将 head->next 的 next 设置为 head 自身，也就是 head->next 变为 head<-next
    // 然后回到上一层递归，将上一层的 head 作为 prev，会发现 prev->head<-next，所以继续反转 prev->head，同时传递最底下的 new_head 直到递归结束
    Node<T>* recursive_reverse_impl(Node<T> *node) {
        if (!node) return nullptr;
        if (!node->next) return node;
        Node<T> *new_head = recursive_reverse_impl(node->next);
        node->next->next = node;
        node->next = nullptr;
        return new_head;
    }

    void recursive_reverse() {
        if (!head) return;
        Node<T> *old_head = head;
        head = recursive_reverse_impl(head);
        tail = old_head;
    }

    ~LinkedList()
    {
        Node<T> *node = head;
        while (node)
        {
            Node<T> *tmp_node = node->next;
            delete node;
            node = tmp_node;
        }
    }
};

void run_tests()
{
    // 测试 1: 基本插入与 tail 指针
    {
        LinkedList<int> list;
        list.push_back(10);
        assert(list.get_back() != nullptr);
        assert(list.get_back()->value == 10);

        list.push_front(5);
        assert(list.get_node_by_index(0)->value == 5);
        assert(list.get_back()->value == 10);
    }

    // 测试 2: 边界删除 (1个元素变0个)
    {
        LinkedList<int> list;
        list.push_back(100);
        list.remove_by_index(0);
        assert(list.get_node_by_index(0) == nullptr);
        assert(list.get_back() == nullptr); // 验证 tail 是否置空
    }

    // 测试 3: 插入到 index 0 (验证 tail)
    {
        LinkedList<int> list;
        list.insert(0, 50);
        assert(list.get_back() != nullptr);
        assert(list.get_back()->value == 50);
    }

    // 测试 4: 按值删除及 times 参数
    {
        LinkedList<int> list;
        list.push_back(1);
        list.push_back(2);
        list.push_back(2);
        list.push_back(3);

        // 删除第二个 '2'
        list.remove_by_value(2, 2);
        assert(list.get_index_by_value(2, 2) == -1);
        assert(list.get_index_by_value(2, 1) == 1);

        // 删除末尾元素验证 tail
        list.remove_by_value(3, 1);
        assert(list.get_back()->value == 2);
    }

    // 测试 5: 连续 pop
    {
        LinkedList<int> list;
        list.push_back(1);
        list.push_back(2);
        list.pop();
        list.pop();
        assert(list.get_back() == nullptr);
    }

    // 测试 8: 专门测试删除头节点和尾节点 (by value)
    {
        LinkedList<int> list;
        list.push_back(10);
        list.push_back(20);
        list.push_back(30);

        // 删除头节点
        list.remove_by_value(10, 1);
        assert(list.get_node_by_index(0)->value == 20);

        // 删除尾节点
        list.remove_by_value(30, 1);
        assert(list.get_back()->value == 20);
        assert(list.get_back()->next == nullptr);
    }

    // 测试越界插入/删除（应静默忽略）
    {
        LinkedList<int> list;
        list.insert(1, 100); // index=1 > size=0 → 应忽略
        assert(list.get_back() == nullptr);

        list.push_back(1);
        list.remove_by_index(5); // 越界 → 忽略
        assert(list.get_back() != nullptr);
    }

    // 测试反转
    {
        LinkedList<int> list;
        list.push_back(1);
        list.push_back(2);
        list.push_back(3);
        list.reverse();
        assert(list.get_node_by_index(0)->value == 3);
        assert(list.get_node_by_index(1)->value == 2);
        assert(list.get_node_by_index(2)->value == 1);
    }
    
    // 测试递归反转
    {
        LinkedList<int> list;
        list.push_back(1);
        list.push_back(2);
        list.push_back(3);
        list.recursive_reverse();
        assert(list.get_node_by_index(0)->value == 3);
        assert(list.get_node_by_index(1)->value == 2);
        assert(list.get_node_by_index(2)->value == 1);
    }

    std::cout << "所有测试用例通过！" << std::endl;
}

int main()
{
    run_tests();
    return 0;
}