题解 | #合并两群能量值#【C语言】
合并两群能量值
https://www.nowcoder.com/practice/d728938f66ac44b5923d4f2e185667ec
题目要求:
合并两个有序递减链表,形成新的递减链表返回。
算法1:遍历插入
解题思路:
- 对于两个A,B有序的链表,我们可以创造一个新链表;
- 将A,B两个链表里面的元素进行单个比较。先放入比较大的;
- 如果A,B链表里面在比较完之后
- 还有一个(有且只有一个)链表有剩余,我们可以直接用指针指向(因为两个链表本来就是有序的)。
实现代码:
struct ListNode* mergeEnergyValues(struct ListNode* l1, struct ListNode* l2 ) {
//创造一个哑结点
struct ListNode* dummy = malloc(sizeof(struct ListNode));
//对结点初始化
dummy->next = NULL;
dummy->val = 0;
struct ListNode* curr = dummy;
while (l1 && l2) {
curr->next = malloc(sizeof(struct ListNode));//每次都需要分配空间
if (l1->val >= l2->val) {
curr->next->val = l1->val;
l1 = l1->next;
} else {
curr->next->val = l2->val;
l2 = l2->next;
}
curr = curr->next;
}
//如果有剩余结点,直接指向
if (l1) {
curr->next = l1;
} else {
curr->next = l2;
}
//返回哑结点的下一个结点
struct ListNode* mergedList = dummy->next;
//释放哑结点
free(dummy);
return mergedList;
}
解题技巧:
在上述代码中,我们使用一个哑节点来作为合并后链表的头节点。哑节点是一个额外的节点,它不存储具体的数据,仅作为一个占位符。我们使用哑节点的目的是为了简化合并链表的操作,确保合并后的链表的头节点始终存在。
在代码中,我们通过malloc(sizeof(struct ListNode))来为哑节点分配内存空间。这样,我们就创建了一个新的节点,并将其地址赋值给curr->next,使得curr->next指向哑节点。
然后,在合并链表的过程中,我们通过操作curr->next来连接其他节点。这样,即使合并后的链表为空,我们也能够通过dummy->next来访问到哑节点之后的节点。
C语言刷题日记 文章被收录于专栏
备战秋招!
查看4道真题和解析

