单向环形链表的增删改查c++完整实现

Category： DSA

写在前面

刚写了双向链表的, 趁热打铁再来一个环形链表的, 这次就有点复杂了, 但是还是可以接受的.

实现环形链表的关键就是不能通过判断是否遍历到空节点来结束循环, 这会导致死循环. 只能用指针是否遍历回到头结点来判断. (就是说第二次来到头结点)

还有就是取余操作的应用, 一般来说, 给定下标需要判断下表是否在链表的节点长度范围内, 但是环形链表有所不同, 任何一个整数都可以作为下标(空节点的环形链表除外).

完整代码见: GitHub;

取余操作的一个坑

先来看一段Python代码: (ipython)

In [1]: 10%3
Out[1]: 1

In [2]: -10%3
Out[2]: 2

没什么问题, 再来到C这边:

#include <stdio.h>

int main(int argc, char const *argv[]) {
    printf("%d\n", 10 % 3);  // 1
    printf("%d\n", -10 % 3); //-1
    return 0;
}

对负数取余竟然不一样了, 这是因为Python的%符号进行的是取模运算, 而C/C++, Java等静态语言采用的是取余运算, 所以使用C++实现环形链表, 就要这样写:

pos = pos < 0 ? pos % len() + len() : pos % len();

节点类-链表类

节点类

和单链表一模一样.

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* _next) : val(x), next(_next) {}
};

环形链表类

class RingSingleLinkedList {
public:
    RingSingleLinkedList() : head(nullptr) {}
    RingSingleLinkedList(int head_val) : head(new ListNode(head_val)) {
        head->next = head; // 一个节点成环
    }
    RingSingleLinkedList(int head_val, vector<int> rest);
    RingSingleLinkedList(vector<int> nodes);
    ~RingSingleLinkedList();

    void print();
    ListNode* first();
    ListNode* last();
    int len();

    // visit by pos
    /* int& operator[](int pos); */
    ListNode* operator[](int pos);
    ListNode* visit(int pos);

    // insert by pos
    void insert(int pos, int val);
    void append(int val);

    // delete by pos
    void pop(int pos);
    void pop_front();

    // delete by value
    void remove(int val, int cnt = 1);           // delete val cnt times
    void modify(int val, int node, int cnt = 1); // modify val->node cnt times
    int find(int node);                          // not found:-1


private:
    ListNode* head;
};

辅助函数

输出格式化

ostream& operator<<(ostream& os, ListNode* lp) {
    if (lp == nullptr) return os << "∅" << endl;
    ListNode* cur = lp;

    auto num_len = [](int num) {
        size_t ans{};
        while (num) ++ans, num /= 10;
        return ans;
    };

    size_t show_len = 4 + num_len(cur->val);
    os << cur->val << " -> ";
    while (cur->next != lp) {
        os << cur->next->val << " -> ";
        show_len += num_len(cur->next->val) + 4;
        cur = cur->next;
    }
    os << " |"s << endl;
    os << "^"s << string(show_len, ' ') << "|"s << endl;
    os << "|" << string(show_len, '_') << "|"s;
    return os << endl;
}

void RingSingleLinkedList::print() { cout << head; }

链表长度

int RingSingleLinkedList::len() {
    if (head == nullptr) return 0; // 重要
    int size = 1;
    auto cur = head;
    while (cur->next != head) ++size, cur = cur->next;

    return size;
}

头尾结点

ListNode* RingSingleLinkedList::first() { return head; }

ListNode* RingSingleLinkedList::last() {
    auto cur = head;
    while (cur->next != head) cur = cur->next;
    return cur;
}

遍历环形链表

ListNode* RingSingleLinkedList::operator[](int pos) {
    if (head == nullptr)
        cout << "Attempt to get value from a NULL RingSingleLinkedList\n";

    pos = pos < 0 ? pos % len() + len() : pos % len();

    auto cur = head;
    while (pos--) cur = cur->next;
    return cur;
}

ListNode* RingSingleLinkedList::visit(int pos) { return this->operator[](pos); }

增加节点

指定位置添加

void RingSingleLinkedList::insert(int pos, int val) {
    if (head == nullptr) {
        head = new ListNode(val);
        head->next = head;
        return;
    }
    pos = pos < 0 ? pos % len() + len() : pos % len();
    if (pos == 0) { // change head
        auto cur = head;
        head = new ListNode(val, cur);
        cur->next = head;
    } else {
        auto pre = head;
        while (--pos) pre = pre->next;

        auto cur = pre->next;
        pre->next = new ListNode(val, cur);
    }
}

void RingSingleLinkedList::append(int val) { insert(0, val); }
// TODO: 一个小bug, 插入第一个节点之后, 再插入第二个节点时, 只能改变头结点,
// 因为取余会导致1变为0

这里要说道说道了, 由于位置可以取任意整数, 所以就要取余, 针对负数还要在取余之后加上len(), 因为C++对负数取余的结果还是一个负数, 并不能到链表的节点长度的范围内.

然后需要注意的一个点就是, 当从head为空节点的状态添加(append)了一次节点, 然后再添加(append)第二个, 就会导致头结点发生变化(后面的测试函数中也有注释).

删除节点

针对位置的删除

void RingSingleLinkedList::pop(int pos) {
    if (head == nullptr) {
        cout << "Attempt to delete a NULL RingSingleLinkedList!" << endl;
        return;
    }
    pos = pos < 0 ? pos % len() + len() : pos % len();
    if (len() == 1) {
        delete head;
        head = nullptr;
        return;
    }
    auto cur = head;
    while (--pos > 0) cur = cur->next; // 只判断 pos 不为零不行
    auto tmp = cur->next;
    cur->next = cur->next->next;
    delete tmp;
}

void RingSingleLinkedList::pop_front() { pop(0); }

针对值的删除

void RingSingleLinkedList::remove(int val, int cnt) {
    int idx;
    do {
        if ((idx = find(val)) == -1) {
            cout << "can not find val " << val << " to delete\n";
            break;
        } else
            pop(idx);
    } while (--cnt);
}

cnt表示删除一个元素多少次

修改元素

void RingSingleLinkedList::modify(int val, int node, int cnt) {
    int idx;
    do {
        if ((idx = find(val)) == -1) {
            cout << "can not find val " << val << " to modify\n";
            break;
        } else {
            /* visit(idx)->val = node; */
            /* (*this)[idx]->val = node; */
            this->operator[](idx)->val = node;
        }
    } while (--cnt);
}

查找元素

int RingSingleLinkedList::find(int node) {
    if (head == nullptr) return -1;
    if (head->val == node) return 0;
    auto cur = head;
    int pos{};
    while (cur->next != head) {
        if (cur->val == node) return pos;
        ++pos;
        cur = cur->next;
    }
    return -1;
}

主函数-测试

#include "Ring_Single_Linked_List.hpp"

// === test func === ===//
void test_ctor() {
    RingSingleLinkedList ll1(12);
    ll1.print();

    RingSingleLinkedList ll2(1, {2, 3, 4});
    ll2.print();

    RingSingleLinkedList ll3({1, 2, 3, 4});
    ll3.print();
    /*
    12 ->  |
    ^      |
    |______|
    1 -> 2 -> 3 -> 4 ->  |
    ^                    |
    |____________________|
    1 -> 2 -> 3 -> 4 ->  |
    ^                    |
    |____________________|
    1 2 3 4 deleted...
    1 2 3 4 deleted...
    12 deleted...
    */
}

void test_fundamental() {

    RingSingleLinkedList ll1({1, 2, 3, 4});
    cout << ll1.len() << endl;
    cout << ll1.first()->val << endl;
    cout << ll1.last()->val << endl;
    /* 4 */
    /* 1 */
    /* 4 */
    /* 1 2 3 4 deleted... */
}

void test_operator_at() {
    RingSingleLinkedList ll1({1, 2, 3, 4});
    cout << ll1[-10]->val << endl;     // 3
    cout << ll1[0]->val << endl;       // 1
    cout << ll1[2]->val << endl;       // 3
    cout << ll1[9]->val << endl;       // 2
    cout << ll1.visit(9)->val << endl; // 2
}

void test_insert_1() {
    RingSingleLinkedList ll1;
    ll1.append(20);
    ll1.append(30);
    ll1.insert(-1, 2);
    ll1.print();
    // TODO: 一个小bug, 插入第一个节点之后, 再插入第二个节点时, 只能改变头结点,
    // 因为取余会导致1变为0
    /* 30 -> 2 -> 20 ->  | */
    /* ^                 | */
    /* |_________________| */
    /* 30 2 20 deleted... */
}

void test_insert_2() {
    RingSingleLinkedList ll1({1, 2, 3, 4});
    ll1.insert(1, 2);
    ll1.print();
    /* 1 -> 2 -> 2 -> 3 -> 4 ->  | */
    /* ^                         | */
    /* |_________________________| */
    /* 1 2 2 3 4 deleted... */
}

void test_pop_1() {
    RingSingleLinkedList ll1({1, 2, 3, 4});
    ll1.pop(1);
    ll1.pop(1);
    ll1.pop(1);
    /* ll1.pop(1); */
    ll1.pop_front();
    ll1.print(); // ∅
}

void test_find() {
    RingSingleLinkedList ll1({1, 2, 3, 4});
    cout << ll1.find(1) << endl; // 0
    cout << ll1.find(3) << endl; // 2
    cout << ll1.find(5) << endl; //-1
}

void test_remove_modify() {
    RingSingleLinkedList ll1({1, 1, 3, 4});
    ll1.modify(1, 23, 2);
    ll1.remove(23, 1);
    ll1.print();
    /* 23 -> 3 -> 4 ->  | */
    /* ^                | */
    /* |________________| */
    /* 23 3 4 deleted... */
}


int main(int argc, char* argv[]) {
    /* test_ctor(); */
    /* test_fundamental(); */
    /* test_operator_at(); */
    test_insert_1();
    /* test_insert_2(); */
    /* test_pop_1(); */
    /* test_find(); */
    /* test_remove_modify(); */
    return 0;
}

小结

环形链表的实现中, 很容易出现死循环, 所以一定要判断好循环跳出的条件.

上篇双向链表增删改查的c++完整实现

下篇牛客网acm模式输入输出11道题目的c++解答(c标准io版)