将两个非递减的有序链表合并为一个非递增的有序链表。 要求结果链表仍使用原来 两个链表的存储空间 , 不另外占用其它的存储空间。表中允许有重复的数据。
时间: 2023-05-17 19:06:53 浏览: 147
以下是合并两个非递减有序链表为一个非递增有序链表的代码实现:
```c
#include <stdio.h>
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
void merge(ListNode* l1, ListNode* l2) {
ListNode *p1 = l1, *p2 = l2;
while (p1 && p2) {
if (p1->val <= p2->val) {
p1 = p1->next;
} else {
ListNode *tmp = p2->next;
p2->next = p1->next;
p1->next = p2;
p2 = tmp;
}
}
if (p2) {
p1->next = p2;
}
}
int main() {
ListNode a[3] = {{1, &a[1]}, {3, &a[2]}, {5, NULL}};
ListNode b[3] = {{2, &b[1]}, {4, &b[2]}, {6, NULL}};
merge(a, b);
for (int i = 0; i < 3; i++) {
printf("%d ", a[i].val);
}
return 0;
}
```
这段代码的思路是,用两个指针 p1 和 p2 分别指向两个链表的头结点,然后比较它们的值,如果 p1 的值小于等于 p2 的值,就将 p1 向后移动一位;否则,将 p2 插入到 p1 的后面,并将 p2 向后移动一位。最后,如果 p2 还有剩余,就将它们接到 p1 的末尾。