已知用c语言编写以head为头指针的带头结点的单链表,将结点x 插入第一个结点值为key的结点之前。
时间: 2023-06-26 21:07:36 浏览: 128
单链表进阶1
可以按照以下步骤实现:
1. 创建一个新的结点x;
2. 遍历链表,找到第一个结点值为key的结点以及其前驱结点;
3. 将新结点x插入到该结点的前面。
代码实现如下:
```c
//定义链表结点结构体
typedef struct ListNode{
int data; //数据域
struct ListNode *next; //指针域
}ListNode, *LinkedList;
//在以head为头指针的带头结点的单链表中将结点x插入第一个结点值为key的结点之前
void InsertNodeBeforeKey(LinkedList head, int key, ListNode *x){
ListNode *p = head->next; //p指向链表第一个结点
ListNode *pre = head; //pre指向p的前驱结点
while(p != NULL && p->data != key){
pre = p;
p = p->next;
}
if(p == NULL){
printf("链表中没有值为%d的结点\n", key);
return;
}
pre->next = x;
x->next = p;
}
```
需要注意的是,在调用该函数前需要先创建一个新结点x,并将其data赋值为需要插入的值。例如,如果要将值为3的结点插入到链表中第一个值为2的结点之前,可以按照以下方式调用该函数:
```c
LinkedList head = (LinkedList)malloc(sizeof(ListNode)); //创建头结点
head->next = NULL;
ListNode *node1 = (ListNode*)malloc(sizeof(ListNode)); //创建第一个结点
node1->data = 1;
node1->next = NULL;
head->next = node1;
ListNode *node2 = (ListNode*)malloc(sizeof(ListNode)); //创建第二个结点
node2->data = 2;
node2->next = NULL;
node1->next = node2;
ListNode *node3 = (ListNode*)malloc(sizeof(ListNode)); //创建需要插入的结点
node3->data = 3;
node3->next = NULL;
InsertNodeBeforeKey(head, 2, node3); //将node3插入到结点值为2的结点之前
```
这样,链表就变成了1->3->2。
阅读全文