使用C语言,用LinkList类型自行建立两个有序的单链表,其中使用头插法创建链表 La,使用尾插法创建链表 Lb。将 La 与 Lb合并,得到有序链表 Lc
时间: 2024-10-29 13:13:17 浏览: 36
连接两个链表(使用链表创建).txt
在C语言中,我们可以使用结构体定义链表节点,并分别通过头插法(头部插入新节点)和尾插法(尾部插入新节点)来构建有序链表La和Lb。以下是具体的步骤:
1. 定义链表节点结构:
```c
typedef struct ListNode {
int data;
struct ListNode* next;
} ListNode;
```
2. 创建头插法链表La:
```c
ListNode* createHeadInsertedList(int arr[], int n) {
ListNode* head = NULL, *current = NULL;
for (int i = 0; i < n; i++) {
ListNode newNode = {arr[i], NULL};
if (!head) {
head = &newNode;
} else {
current->next = &newNode;
}
current = &newNode;
}
return head;
}
```
3. 创建尾插法链表Lb:
```c
ListNode* createTailInsertedList(int arr[], int n) {
ListNode* tail = NULL, *current = NULL;
for (int i = 0; i < n; i++) {
ListNode newNode = {arr[i], NULL};
if (!tail) {
tail = &newNode;
} else {
current->next = tail;
}
current = tail;
tail = &newNode;
}
return tail;
}
```
4. 合并两个链表(升序合并):
```c
ListNode* mergeSortedLists(ListNode* la, ListNode* lb) {
if (!la) return lb;
if (!lb || la->data <= lb->data) {
ListNode temp = la;
la = la->next;
free(temp);
return mergeSortedLists(la, lb);
} else {
ListNode temp = lb;
lb = lb->next;
free(temp);
return mergeSortedLists(la, lb);
}
}
```
5. 最终得到有序链表Lc:
```c
ListNode* createCombinedList(int arrLa[], int lenLa, int arrLb[], int lenLb) {
ListNode* la = createHeadInsertedList(arrLa, lenLa);
ListNode* lb = createTailInsertedList(arrLb, lenLb);
return mergeSortedLists(la, lb);
}
```
阅读全文