用c语言表达将两个递增的有序表合并为一个递增的有序表,要求结果链表仍然使用原来链表的存储空间,不另外占用其他的存储空间。表中不允许有重复的元素。
时间: 2024-10-14 12:17:25 浏览: 34
在C语言中,可以使用归并排序的思想结合双指针技术来合并两个递增的有序链表。这里假设我们有两个头结点为`head1`和`head2`的链表,并且它们都已排序。以下是合并过程的一个示例算法:
```c
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
ListNode* mergeTwoLists(ListNode* head1, ListNode* head2) {
// 如果任一链表为空,直接返回另一个链表的头节点
if (head1 == NULL) return head2;
if (head2 == NULL) return head1;
// 定义一个新的头节点和两个指针,初始指向当前列表的头部
ListNode* dummy = (ListNode*)malloc(sizeof(ListNode)); // 创建一个虚拟头节点,用于合并操作
ListNode* tail = dummy; // 尾节点指向dummy
ListNode* cur1 = head1;
ListNode* cur2 = head2;
while (cur1 != NULL && cur2 != NULL) {
// 比较两个指针所指向的值,选择较小的那个添加到新链表中
if (cur1->val < cur2->val) {
tail->next = cur1;
tail = cur1;
cur1 = cur1->next;
} else {
tail->next = cur2;
tail = cur2;
cur2 = cur2->next;
}
}
// 如果还有剩余的链表,将其连接到新链表的尾部
if (cur1 != NULL) {
tail->next = cur1;
} else {
tail->next = cur2;
}
// 返回新的合并后的链表头部(即虚拟头节点)
return dummy->next;
}
```
这个函数不会额外分配内存,而是利用原有的链表空间进行合并。
阅读全文