设计一算法,实现将一个递减的数组 A[0..n-1]和一个带头结点的递增单链表B合并成一个带头结点的递增链表C。
时间: 2023-03-26 09:01:41 浏览: 75
可以使用归并排序的思想,从数组和链表的末尾开始比较大小,将较大的元素插入到链表C的头部,直到数组和链表中的所有元素都被插入到链表C中。具体实现可以参考以下代码:
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* mergeArrayAndList(int A[], int n, ListNode* B) {
ListNode* dummy = new ListNode();
ListNode* cur = dummy;
int i = n - 1;
while (i >= && B) {
if (A[i] > B->val) {
cur->next = new ListNode(A[i]);
i--;
} else {
cur->next = new ListNode(B->val);
B = B->next;
}
cur = cur->next;
}
while (i >= ) {
cur->next = new ListNode(A[i]);
cur = cur->next;
i--;
}
while (B) {
cur->next = new ListNode(B->val);
cur = cur->next;
B = B->next;
}
return dummy->next;
}
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)