链表的头插法和尾插法

链表的头插法和尾插法是两种常见的链表创建方法。

头插法是指将新节点插入到链表的头部。具体步骤如下：
1. 创建一个头节点，并将其指针域指向NULL。
2. 循环读取数据，创建新节点，并将新节点的指针域指向头节点的下一个节点。
3. 将头节点的指针域指向新节点，完成插入操作。

尾插法是指将新节点插入到链表的尾部。具体步骤如下：
1. 创建一个头节点，并将其指针域指向NULL。
2. 创建一个尾节点，并将其指针域指向NULL。
3. 循环读取数据，创建新节点，并将尾节点的指针域指向新节点。
4. 将尾节点更新为新节点，完成插入操作。

头插法和尾插法的区别在于插入位置的不同。头插法将新节点插入到链表的头部，而尾插法将新节点插入到链表的尾部。这两种方法都可以用来创建链表，具体选择哪种方法取决于实际需求。

相关问题

创建链表 头插法和尾插法

链表是一种数据结构，其中的元素（节点）不连续存储，而是通过链接（指针）彼此连接。创建链表时，头插法和尾插法是两种常用的节点插入方法：

1. **头插法（Head Insertion）**：
- 这种方法是在链表的头部插入新节点。具体步骤如下：
- 创建新节点，并将它的 `next` 指针指向当前链表的头节点。
- 如果链表为空，则新节点同时是头和尾。
- 否则，将旧的头节点的 `next` 指针更新为新节点。

2. **尾插法（Tail Insertion）**：
- 在尾部插入节点的过程通常是这样：
- 创建新节点。
- 如果链表为空，新节点既是头又是尾。
- 否则，遍历链表找到最后一个节点，将其 `next` 指针指向新节点。

头插法常用于实现队列等数据结构，因为它可以在常数时间内添加新的元素到链表的开始。而尾插法则常用于实现栈或需要在末尾频繁添加元素的情况，因为遍历整个链表来找到尾节点的时间复杂度是 O(n)。

链表的头插法和尾插法的示意图和代码

链表的头插法和尾插法是两种常见的链表插入操作。

头插法：新节点插入到链表的头部，成为新的头节点。

示意图：

插入前：   插入后：
  head       new_node
    |           |
    V           V
   node1      node1
    |           |
    V           V
   node2      node2
    |           |
    V           V
   node3      node3

代码实现：

// 头插法
void insert_head(ListNode *&head, int val) {
    ListNode *new_node = new ListNode(val);
    new_node->next = head;
    head = new_node;
}

尾插法：新节点插入到链表的尾部，成为新的尾节点。

示意图：

插入前：      插入后：
   head          head
     |             |
     V             V
   node1         node1
     |             |
     V             V
   node2         node2
     |             |
     V             V
   node3         new_node
                   |
                   V
                 node3

代码实现：

// 尾插法
void insert_tail(ListNode *&head, int val) {
    ListNode *new_node = new ListNode(val);
    if (head == nullptr) {
        head = new_node;
    } else {
        ListNode *p = head;
        while (p->next != nullptr) {
            p = p->next;
        }
        p->next = new_node;
    }
}

其中，`ListNode` 是链表节点的定义，包含一个 `val` 域和一个 `next` 指针，指向下一个节点。