头插法尾插法建立单链表

单链表是一种常见的数据结构，它由若干个结点组成，每个结点包含一个数据域和一个指向下一个结点的指针域。单链表的建立有两种方法：头插法和尾插法。

头插法建立单链表的过程是：首先创建一个头结点，然后依次读入数据，每读入一个数据就创建一个新结点，并将新结点插入到头结点之后，最后返回头结点的指针即可。

尾插法建立单链表的过程是：首先创建一个头结点，然后依次读入数据，每读入一个数据就创建一个新结点，并将新结点插入到链表的尾部，最后返回头结点的指针即可。

头插法和尾插法的区别在于插入新结点的位置不同，头插法是插入到头结点之后，而尾插法是插入到链表的尾部。头插法和尾插法都可以建立单链表，但是它们的时间复杂度不同，头插法的时间复杂度为O(n)，而尾插法的时间复杂度为O(1)。

相关问题

用头插法或尾插法建立单链表

单链表是一种常见的数据结构，可以用头插法或尾插法来建立。其中，头插法是将新节点插入到链表的头部，而尾插法则是将新节点插入到链表的尾部。

以头插法为例，建立单链表的步骤如下：
1. 创建一个头节点，并将其指针域置为空。
2. 读入第一个节点的数据，创建一个新节点，并将其指针域指向头节点的下一个节点。
3. 将头节点的指针域指向新节点。
4. 重复步骤2和3，直到所有节点都被插入到链表中。

以尾插法为例，建立单链表的步骤如下：
1. 创建一个头节点，并将其指针域置为空。
2. 读入第一个节点的数据，创建一个新节点，并将其指针域指向空。
3. 将头节点的指针域指向新节点。
4. 将新节点赋值给一个临时变量p。
5. 重复步骤2到4，直到所有节点都被插入到链表中。

c++利用头插法或尾插法建立单链表

在C++中，头插法（Insertion at the beginning）和尾插法（Insertion at the end）是创建单链表常用的方法。这里分别给出这两个操作的基本实现：

1. **头插法**（Insertion at the beginning）:

class Node {
public:
    int data;
    Node* next;
    
    // 构造函数
    Node(int value) : data(value), next(nullptr) {}
};

class LinkedList {
private:
    Node* head;

public:
    // 插入新元素到头部
    void insertAtBegin(int value) {
        Node* newNode = new Node(value);
        newNode->next = head; // 新节点指向当前头
        head = newNode;       // 更新头指针
    }

    // 其他链表操作...
};

在这个例子中，`insertAtBegin`方法首先创建一个新的节点，然后将它的`next`指针指向当前的头节点，最后更新头指针。

2. **尾插法**（Insertion at the end）:

void insertAtEnd(int value) {
    if (head == nullptr) {
        head = new Node(value); // 如果链表为空，直接插入
    } else {
        Node* temp = head;
        while (temp->next != nullptr) { // 遍历找到末尾
            temp = temp->next;
        }
        temp->next = new Node(value); // 在最后一个节点之后插入新节点
    }
}

这个`insertAtEnd`方法检查链表是否为空，如果空则直接在头插入。否则，它通过一个循环找到链表的末尾，并在其之后插入新的节点。