用C语言将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍然使用原来两个链表的存储空间,不另外占用其他的存储空间。表中不允许有重复的数据。 例如:LA={2,4,5,9,18},LB={3,5,12,16} 合并后 LA={2,3,4,5,9,12,16,18}
时间: 2024-10-14 19:15:02 浏览: 32
在C语言中合并两个递增有序链表且保持原节点不变,可以采用双指针法。假设链表的头结点分别为`headA`和`headB`,我们可以创建一个新的空链表`result`作为合并后的链表。
以下是步骤:
1. 初始化三个指针,`p1`指向`headA`,`p2`指向`headB`,以及`resultHead`指向`result`的头结点(初始为空)。
2. 比较`p1`和`p2`所指向的节点值。如果`p1`的值小于等于`p2`的值,说明当前`headA`的节点更小,将其插入到`result`链表之后,并将`p1`移动到下一个节点;否则,将`p2`的节点插入到`result`链表之后,然后将`p2`移动到下一个节点。
3. 重复步骤2,直到其中一个链表遍历完。此时,如果还有剩余节点未处理,直接将另一个链表剩下的部分添加到`result`链表上。
4. 最后,`resultHead`就是合并后链表的头结点。
下面是伪代码形式:
```c
struct ListNode* mergeSortedLists(struct ListNode* headA, struct ListNode* headB) {
struct ListNode* resultHead = NULL;
struct ListNode* p1 = headA;
struct ListNode* p2 = headB;
struct ListNode* currentResult = resultHead;
while (p1 && p2) {
if (p1->val <= p2->val) {
currentResult->next = p1;
currentResult = p1;
p1 = p1->next;
} else {
currentResult->next = p2;
currentResult = p2;
p2 = p2->next;
}
}
// 如果有一个链表还剩节点,将其添加到结果链表尾部
if (p1) {
currentResult->next = p1;
} else if (p2) {
currentResult->next = p2;
}
return resultHead;
}
```
阅读全文