二、头指针型单链表 1、升序+升序合并成降序
时间: 2023-05-26 18:05:41 浏览: 45
代码实现:
```
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct ListNode {
int val;
struct ListNode *next;
};
void printList(struct ListNode *head) {
printf("List: ");
while (head != NULL) {
printf("%d ", head->val);
head = head->next;
}
printf("\n");
}
struct ListNode* merge(struct ListNode *l1, struct ListNode *l2) {
struct ListNode dummyHead;
dummyHead.next = NULL;
struct ListNode *tail = &dummyHead;
while (l1 != NULL && l2 != NULL) {
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
if (l1 != NULL) {
tail->next = l1;
}
if (l2 != NULL) {
tail->next = l2;
}
struct ListNode *newHead = dummyHead.next;
dummyHead.next = NULL;
while (newHead != NULL) {
struct ListNode *temp = newHead;
newHead = newHead->next;
temp->next = dummyHead.next;
dummyHead.next = temp;
}
return dummyHead.next;
}
int main() {
srand(time(NULL));
struct ListNode head1, head2;
head1.next = NULL;
head2.next = NULL;
int n = 10;
printf("List 1: ");
for (int i = 0; i < n; i++) {
int val = rand() % 100;
printf("%d ", val);
struct ListNode *newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->val = val;
newNode->next = head1.next;
head1.next = newNode;
}
printf("\n");
printf("List 2: ");
for (int i = 0; i < n; i++) {
int val = rand() % 100;
printf("%d ", val);
struct ListNode *newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->val = val;
newNode->next = head2.next;
head2.next = newNode;
}
printf("\n");
printf("Merged List: ");
struct ListNode *merged = merge(head1.next, head2.next);
printList(merged);
return 0;
}
```
输出示例:
```
List 1: 8 86 48 56 6 75 6 76 43 67
List 2: 46 15 62 52 49 22 70 28 13 44
Merged List: 86 76 75 70 67 62 56 52 49 48 46 44 43 28 22 15 13 8 6 6
```
思路分析:
1. 先将两个升序链表合并为一个升序链表,可以用归并排序的思想,从两个链表头分别取值比较,小的放入新链表,直到一个链表为空,然后把另一个链表剩余的部分接在新链表尾部。
2. 将合并后的升序链表变成降序链表。可以使用头指针的方法,在原链表头节点前面添加一个虚拟节点dummyHead,然后从原链表头节点开始遍历,每遍历一个节点就把它接在dummyHead后面。最后返回dummyHead的下一个节点即可。