将两个单链表合并为一个单链表。结果如下图所示:L1:a+b+c+d+e+f+g+h+ L2:1+2+3+4+5 L1和L2合并产生L3 L3:a+1+b+2+c+3+d+4+e+5+f+g+h
时间: 2023-11-12 18:09:02 浏览: 222
数据结构与算法 c++实现 两个单链表合并为一个单链表,两个表的元素交错排列,新表用原表结点的内存空间 按元素序列的奇偶分割单
5星 · 资源好评率100%
将两个单链表合并为一个单链表的过程可以通过递归实现。具体步骤如下:
1. 如果其中一个链表为空,则直接返回另一个链表。
2. 如果两个链表都不为空,则比较两个链表头结点的值,将值较小的头结点作为合并后链表的头结点。
3. 将值较小的头结点的 next 指针指向递归调用合并函数后返回的链表。
4. 返回合并后的链表。
根据上述步骤,可以得到以下代码实现:
```C++
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == nullptr) {
return l2;
}
if (l2 == nullptr) {
return l1;
}
if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
```
其中,ListNode 是单链表的结构体,包含 val 和 next 两个成员变量,分别表示结点的值和指向下一个结点的指针。
阅读全文