玩转单链表：头插法和尾插法详解

一、基本概念

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

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

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

二、头叉法

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

#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;
}

 

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

三、尾插法

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

代码

#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;
}

 

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

参考：

创建单链表的头插法与尾插法详解_Descosmos的博客-****博客_头插法建立单链表

头插法详细图解_One Piece&的博客-****博客_头插法

C++单链表的创建：头插法与尾插法_fakerth的博客-****博客_c++头插法建立单链表