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

备战秋招!

全部评论

相关推荐

11-15 18:39
已编辑
西安交通大学 Java
全村最靓的仔仔:卧槽,佬啥bg呢,本也是西交么
点赞 评论 收藏
分享
2 1 评论
分享
牛客网
牛客企业服务