写一个链表插入操作

链表插入操作可以分为两种情况：在链表头插入和在链表中间或尾部插入。

1. 在链表头插入：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

void insertAtHead(ListNode *&head, int val) {
    ListNode *node = new ListNode(val);
    node->next = head;
    head = node;
}

2. 在链表中间或尾部插入：

void insertAfter(ListNode *prev, int val) {
    if (prev == NULL) {
        return; // 如果前置节点为空，什么也不做
    }
    ListNode *node = new ListNode(val);
    node->next = prev->next;
    prev->next = node;
}

其中，`prev`表示要插入节点的前置节点。如果`prev`为空，则说明要插入到链表中间或尾部的位置不存在，直接返回即可。否则，新建一个节点并将其插入到`prev`后面即可。

相关问题

用c+＋写一个线性链表插入函数

### 回答1：
好的，以下是使用C语言编写一个线性链表插入函数的示例代码：

#include <stdio.h>
#include <stdlib.h>

struct Node {
   int data;
   struct Node *next;
};

struct Node* insert(struct Node* head, int value) {
   struct Node* newNode = (struct Node*) malloc(sizeof(struct Node)); // 为新节点分配内存空间
   newNode->data = value;
   newNode->next = NULL;

   if (head == NULL) { // 链表为空，直接将新节点设为头节点
      head = newNode;
   } else { // 在链表尾部插入新节点
      struct Node* current = head;
      while (current->next != NULL) {
         current = current->next;
      }
      current->next = newNode;
   }

   return head;
}

int main() {
   struct Node* head = NULL; // 初始链表为空
   head = insert(head, 1); // 插入值为1的节点
   head = insert(head, 2); // 插入值为2的节点
   head = insert(head, 3); // 插入值为3的节点

   // 遍历链表并输出节点的值
   struct Node* current = head;
   while (current != NULL) {
      printf("%d ", current->data);
      current = current->next;
   }

   return 0;
}

这段代码创建了一个`Node`结构体表示链表中的节点，其中`data`成员表示节点的值，`next`成员指向下一个节点。`insert`函数接收一个头指针和一个值，如果链表为空则将新节点设为头节点，否则在链表的尾部插入新节点。`main`函数创建一个空链表并插入了三个节点，然后遍历链表并输出节点的值。

### 回答2：
线性链表是一种常见的数据结构，可以用于存储和操作一系列数据元素。插入函数是用来在链表中插入新的节点的操作。

以下是用C++编写的一个简单的线性链表插入函数的代码：

#include <iostream>

// 定义链表节点结构
struct Node {
    int data; // 节点存储的数据
    Node* next; // 指向下一个节点的指针
};

// 插入新节点到链表中
void insert(Node** head, int newData) {
    // 创建新节点
    Node* newNode = new Node();
    newNode->data = newData;
    newNode->next = NULL;

    // 如果链表为空，则将新节点置为头节点
    if (*head == NULL) {
        *head = newNode;
        return;
    }

    // 找到链表末尾的节点
    Node* lastNode = *head;
    while (lastNode->next != NULL) {
        lastNode = lastNode->next;
    }

    // 在链表末尾插入新节点
    lastNode->next = newNode;
}

// 测试插入函数
int main() {
    // 创建一个空链表头节点
    Node* head = NULL;

    // 插入一系列数据到链表中
    insert(&head, 1);
    insert(&head, 2);
    insert(&head, 3);
    insert(&head, 4);

    // 遍历并打印链表中的数据
    Node* currentNode = head;
    while (currentNode != NULL) {
        std::cout << currentNode->data << " ";
        currentNode = currentNode->next;
    }

    return 0;
}

这个插入函数将新节点添加到链表的末尾。首先，它检查链表是否为空，如果为空，则将新节点置为头节点。如果链表不为空，则找到链表的末尾节点，然后将新节点插入到末尾节点的后面。

在上面的测试代码中，我们使用插入函数向链表中插入了四个节点，并最终遍历并打印了链表中的数据（1 2 3 4）。

### 回答3：
以下是用C++编写的线性链表插入函数：

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

void insertNode(Node*& head, int value) {
    Node* newNode = new Node;
    newNode->data = value;
    newNode->next = nullptr;

    // 如果链表为空
    if (head == nullptr) {
        head = newNode;
    }
    else {
        Node* current = head;
        Node* previous = nullptr;

        while (current != nullptr && current->data < value) {
            previous = current;
            current = current->next;
        }

        // 插入节点
        if (previous == nullptr) {
            newNode->next = head;
            head = newNode;
        }
        else {
            previous->next = newNode;
            newNode->next = current;
        }
    }
}

int main() {
    Node* head = nullptr;

    insertNode(head, 10);
    insertNode(head, 5);
    insertNode(head, 8);
    insertNode(head, 12);

    // 打印链表
    Node* current = head;
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;

    return 0;
}

该插入函数接受一个指向链表头节点的指针和一个要插入的值。如果链表为空，直接将新节点作为头节点。否则，遍历链表找到合适的位置插入新节点。最后，打印整个链表以验证插入操作是否成功。

以上就是用C++编写的线性链表插入函数的示例，希望对您有帮助！

用Python写一个链表

可以使用Python语言实现链表数据结构，具体实现方法如下：

1. 定义一个节点类，包含两个属性：数据和指向下一个节点的指针。

class Node:
def __init__(self, data):
self.data = data
self.next = None

2. 定义一个链表类，包含一个头节点和链表长度。

class LinkedList:
def __init__(self):
self.head = None
self.length =

3. 实现链表的插入操作，包括在链表头部插入节点和在链表尾部插入节点。

# 在链表头部插入节点
def insert_at_head(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
self.length += 1

# 在链表尾部插入节点
def insert_at_tail(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
else:
current_node = self.head
while current_node.next is not None:
current_node = current_node.next
current_node.next = new_node
self.length += 1

4. 实现链表的删除操作，包括删除指定节点和删除链表头部节点。

# 删除指定节点
def delete_node(self, data):
if self.head is None:
return
if self.head.data == data:
self.head = self.head.next
self.length -= 1
return
current_node = self.head
while current_node.next is not None:
if current_node.next.data == data:
current_node.next = current_node.next.next
self.length -= 1
return
current_node = current_node.next

# 删除链表头部节点
def delete_at_head(self):
if self.head is None:
return
self.head = self.head.next
self.length -= 1

5. 实现链表的搜索操作，包括查找指定节点和查找链表中是否存在指定数据。

# 查找指定节点
def search_node(self, data):
current_node = self.head
while current_node is not None:
if current_node.data == data:
return current_node
current_node = current_node.next
return None

# 查找链表中是否存在指定数据
def contains(self, data):
current_node = self.head
while current_node is not None:
if current_node.data == data:
return True
current_node = current_node.next
return False

以上就是用Python实现链表的基本操作，可以根据需要进行扩展和优化。