单链表的头插法与尾插法

青旅半醒 2024-03-30 12:09 102阅读 0赞

#### 一、基本概念 ####

单链表是一种链式存储结构，它由若干个节点组成，每个节点都有一个指针指向下一个节点。链表的插入操作分为头插法和尾插法。

头插法：新节点插入到链表的头部。具体操作是先使新节点的next指针指向原来的头节点，再让头节点指向新的节点。

尾插法：新节点插入到链表的尾部。具体操作是先找到链表的尾节点，让尾节点的next指针指向新的节点，再把新节点变为尾节点。

#### 二、头叉法 ####

该方法从一个空链表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头。采用头插法创建单链表时，读入数据的顺序与生成单链表的元素顺序是相反的。

![05297a1ddc654970a90a6fb7e7239c8e.png][]

#include <iostream>
    using namespace std;
    
    // 定义单链表结构体
    struct ListNode {
        int val;
        ListNode* next;
        ListNode(int x) : val(x), next(nullptr) {}
    };
    
    ListNode* insertAtHead(ListNode* head, int value) {
        ListNode* newNode = new ListNode(value);
        newNode->next = head;
        return newNode;
    }
    
    int main() {
        ListNode* head = nullptr;  // 初始化头指针为空指针
        for (int i = 0; i < 5; i++) {
            head = insertAtHead(head, i);  // 插入节点到头部
        }
    
        // 遍历单链表，输出节点值
        ListNode* cur = head;
        while (cur) {
            cout << cur->val << "->";
            cur = cur->next;
        }
        cout << "nullptr" << endl;
    
        return 0;
    }

![62a36f60313941638aff34dfd6c96a67.png][]

以上代码实现了单链表的头插法，主要思想是每次将新节点插入到链表头部，并更新头指针。在本示例中，我们先初始化头指针为空指针，然后依次插入5个节点。最后遍历单链表，输出每个节点值。

#### 三、尾插法 ####

该方法将新结点插入到当前链表的表尾，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。

![70][]

代码

#include <iostream>
    using namespace std;
    
    // 定义单链表结构体
    struct ListNode {
        int val;
        ListNode* next;
        ListNode(int x) : val(x), next(nullptr) {}
    };
    
    ListNode* insertAtTail(ListNode* head, int value) {
        ListNode* newNode = new ListNode(value);
        if (head == nullptr) {  // 链表为空，直接将新节点设为头指针并返回
            head = newNode;
        } else {  // 链表不为空
            ListNode* cur = head;
            while (cur->next) {  // 找到最后一个节点
                cur = cur->next;
            }
            cur->next = newNode;  // 将新节点连接到最后一个节点的next
        }
        return head;
    }
    
    int main() {
        ListNode* head = nullptr;  // 初始化头指针为空指针
        for (int i = 0; i < 5; i++) {
            head = insertAtTail(head, i);  // 插入节点到尾部
        }
    
        // 遍历单链表，输出节点值
        ListNode* cur = head;
        while (cur) {
            cout << cur->val << "->";
            cur = cur->next;
        }
        cout << "nullptr" << endl;
    
        return 0;
    }

![34f49f5889a94419995cf751f8a44874.png][]

以上代码实现了单链表的尾插法，主要思想是每次将新节点插入到链表尾部。在本示例中，我们先初始化头指针为空指针，然后依次插入5个节点。最后遍历单链表，输出每个节点值。

参考：

[创建单链表的头插法与尾插法详解\_Descosmos的博客-CSDN博客\_头插法建立单链表][Descosmos_-CSDN]

[头插法详细图解\_One Piece&的博客-CSDN博客\_头插法][One Piece_-CSDN]

[C++单链表的创建：头插法与尾插法\_fakerth的博客-CSDN博客\_c++头插法建立单链表][C_fakerth_-CSDN_c]

[05297a1ddc654970a90a6fb7e7239c8e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/4a1e18832aa94d96aaa888b2c73ae08f.png
[62a36f60313941638aff34dfd6c96a67.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/e6197123b4374f12a0fd47221331e3f0.png
[70]: https://img-blog.csdn.net/20180926194847575?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDI4OTg1/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[34f49f5889a94419995cf751f8a44874.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/e5bafc6a09084cd7b4742b369574f274.png
[Descosmos_-CSDN]: https://blog.csdn.net/qq_41028985/article/details/82859199
[One Piece_-CSDN]: https://blog.csdn.net/cainiaofu/article/details/108434499
[C_fakerth_-CSDN_c]: https://blog.csdn.net/weixin_43912621/article/details/117479998