C语言输入无序的元素,分别建立两个有3个结点的逆序单链表(有头结点)(显示排序后的链表),合并两个单链表使之仍然有序,显示合并后的单链表。
时间: 2024-12-10 10:32:13 浏览: 23
在C语言中,为了实现这个功能,我们需要做以下几个步骤:
1. **输入并建立逆序单链表**:
首先,你需要创建一个结构体表示链表节点,包含一个数据域和一个指向下一个节点的指针。然后编写函数分别读取两个逆序排列的链表元素,并插入到新的链表中,保持逆序。
```c
typedef struct Node {
int data;
struct Node* next;
} Node;
void insertReverse(Node** head, int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = *head;
*head = newNode;
}
```
2. **合并两个逆序链表**:
创建一个新的链表来存储结果。遍历这两个逆序链表,每次从每个链表中取出最小的数据节点,将其添加到新链表的头部。注意,因为是逆序的,所以实际上是在找到当前链表的最小值之后再取下一个链表的最大值。
```c
Node* mergeSortedLists(Node* list1, Node* list2) {
if (!list1 && !list2) return NULL;
if (!list1 || (!list2 && list1->data <= list2->data)) {
return list1;
}
Node* mergedHead = list2;
list2 = list2->next;
while (list1 && list2) {
if (list1->data <= list2->data) {
mergedHead->next = list1;
list1 = list1->next;
} else {
mergedHead->next = list2;
list2 = list2->next;
}
mergedHead = mergedHead->next;
}
mergedHead->next = list1 ? list1 : list2; // 将未遍历完的链表接上
return mergedHead;
}
```
3. **显示排序后的链表**:
最后,遍历合并后的链表并打印节点的数据。
```c
void printList(Node* node) {
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
int main() {
Node* list1_head = ...; // 初始化第一个逆序链表
Node* list2_head = ...; // 初始化第二个逆序链表
Node* mergedHead = mergeSortedLists(list1_head, list2_head);
printList(mergedHead);
return 0;
}
```
阅读全文