题解 | #合并两群能量值#【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语言刷题日记 文章被收录于专栏
备战秋招!