C++ 自定义单向链表 ListNode详情

下面我将为您详细讲解“C++自定义单向链表ListNode详情”的完整攻略。

一、什么是自定义单向链表？

自定义单向链表是一种数据结构，它是由若干个节点（Node）构成的链式存储结构，其中每个节点都包含一个数据域和一个指针域，指针域指向下一个节点。与数组不同，链表的大小可以动态变化，并且可以随时插入和删除节点。

二、自定义单向链表的实现

1. 定义节点结构体

我们可以使用结构体来定义节点类型，节点应该包含一个数据域和一个指针域，指针域指向下一个节点。下面是一个节点结构体的定义示例：

struct ListNode {
    int val; // 数据域
    ListNode *next; // 指针域
    ListNode(int x) : val(x), next(NULL) {}
};

这个结构体包含了一个int类型的数据val和一个指向ListNode类型的指针next，初始化时next指针为空。

2. 添加节点

在自定义单向链表中，添加节点可以通过将新节点插入到链表的末尾，或者将新节点插入到链表的任意位置。下面是在链表末尾添加新节点的示例代码：

ListNode* addNode(ListNode* head, int val) {
    ListNode *newNode = new ListNode(val);
    ListNode *cur = head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = newNode;
    return head;
}

这个函数接收链表头节点的指针head和待插入节点的值val，返回新的链表头节点的指针。它会遍历整个链表，找到最后一个节点cur，然后在cur的next指针处插入一个新节点newNode。

3. 删除节点

删除节点可以通过遍历链表找到要删除的节点，然后将该节点的前一个节点的next指针指向该节点的后一个节点。下面是在链表中删除指定节点的示例代码：

ListNode* deleteNode(ListNode* head, int val) {
    ListNode *cur = head, *prev = NULL;
    while (cur != NULL && cur->val != val) {
        prev = cur;
        cur = cur->next;
    }
    if (prev == NULL) {
        head = head->next;
    } else {
        prev->next = cur->next;
    }
    delete cur;
    return head;
}

这个函数接收链表头节点的指针head和待删除节点的值val，返回新的链表头节点的指针。它会遍历整个链表，找到要删除的节点cur和该节点的前一个节点prev，然后将prev的next指针指向cur的后一个节点，最后删除cur节点。

三、示例应用

下面给出两个示例：

1. 使用自定义单向链表实现队列

队列是一种先进先出的数据结构，我们可以使用自定义单向链表来实现队列。下面是一些函数的示例实现：

// 队列结构体
struct MyQueue {
    ListNode *front, *rear; // 队列头节点和尾节点
    int size; // 队列大小
    MyQueue() : front(NULL), rear(NULL), size(0) {}
};

// 入队
void queuePush(MyQueue* q, int val) {
    if (q->rear == NULL) { // 队列为空
        q->front = q->rear = new ListNode(val);
    } else {
        q->rear->next = new ListNode(val);
        q->rear = q->rear->next;
    }
    q->size++;
}

// 出队
void queuePop(MyQueue* q) {
    if (q->front == NULL) return;
    ListNode *temp = q->front;
    q->front = q->front->next;
    if (q->front == NULL) {
        q->rear = NULL;
    }
    delete temp;
    q->size--;
}

// 获取队头元素
int queueFront(MyQueue* q) {
    return q->front == NULL ? -1 : q->front->val;
}

// 获取队尾元素
int queueRear(MyQueue* q) {
    return q->rear == NULL ? -1 : q->rear->val;
}

// 判断队列是否为空
bool queueEmpty(MyQueue* q) {
    return q->size == 0;
}

// 获取队列大小
int queueSize(MyQueue* q) {
    return q->size;
}

2. 使用自定义单向链表实现链式哈希表

链式哈希表是一种数据结构，它可以高效地实现查找、插入和删除操作。我们可以使用自定义单向链表来实现链式哈希表中的链表结构。下面是一些函数的示例实现：

// 哈希表结点结构体
struct HashNode {
    int key, value;
    HashNode *next;
    HashNode(int k, int v) : key(k), value(v), next(NULL) {}
};

// 哈希表结构体
struct MyHashMap {
    vector<HashNode*> data;
    const int len = 10000;
    MyHashMap() : data(len) {}

    // 哈希函数
    int hash(int key) {
        return key % len;
    }

    // 获取指定键对应的节点指针
    HashNode* getNode(int key) {
        int id = hash(key);
        HashNode *cur = data[id];
        while (cur != NULL) {
            if (cur->key == key) {
                break;
            }
            cur = cur->next;
        }
        return cur;
    }

    // 插入键值对
    void put(int key, int value) {
        int id = hash(key);
        HashNode *cur = data[id];
        while (cur != NULL) {
            if (cur->key == key) {
                cur->value = value;
                return;
            }
            cur = cur->next;
        }
        HashNode *newNode = new HashNode(key, value);
        newNode->next = data[id];
        data[id] = newNode;
    }

    // 获取指定键对应的值
    int get(int key) {
        HashNode *node = getNode(key);
        return node == NULL ? -1 : node->value;
    }

    // 删除指定键
    void remove(int key) {
        int id = hash(key);
        HashNode *cur = data[id], *prev = NULL;
        while (cur != NULL) {
            if (cur->key == key) {
                if (prev == NULL) {
                    data[id] = cur->next;
                } else {
                    prev->next = cur->next;
                }
                delete cur;
                return;
            }
            prev = cur;
            cur = cur->next;
        }
    }
};

以上是自定义单向链表的详细介绍和应用示例，希望对您有所帮助。