当前位置: 首页> 汽车> 报价 > 惠州双语网站建设费用_甘肃做网站_本地推广最有效的方法_优化外包哪里好

惠州双语网站建设费用_甘肃做网站_本地推广最有效的方法_优化外包哪里好

时间:2025/7/9 6:45:29来源:https://blog.csdn.net/weixin_64593595/article/details/143954807 浏览次数: 0次
惠州双语网站建设费用_甘肃做网站_本地推广最有效的方法_优化外包哪里好

合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

示例 2:

输入:l1 = [], l2 = []
输出:[]

示例 3:

输入:l1 = [], l2 = [0]
输出:[0]

方法一:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode *dummy = new ListNode(0);ListNode *current = dummy;while (list1 != nullptr && list2 != nullptr) {if (list1->val <= list2->val) {current->next = list1;list1 = list1->next;} else {current->next = list2;list2 = list2->next;}current = current->next;}if (list1 != nullptr) {current->next = list1;} else {current->next = list2;}return dummy->next;}
};
  • 条件:list1 != nullptr && list2 != nullptr

    • 只要两个链表都不为空,就可以比较它们的当前节点值。
  • 分支逻辑:

    1. 如果 list1->val 小于等于 list2->val
      • list1 的当前节点连接到合并链表的尾部,即 current->next = list1
      • 移动 list1 指针到下一个节点,即 list1 = list1->next
    2. 否则:
      • list2 的当前节点连接到合并链表的尾部,即 current->next = list2
      • 移动 list2 指针到下一个节点,即 list2 = list2->next
  • 指针更新:

    • 无论进入哪个分支,都需要将 current 移动到当前链表的末尾:current = current->next
  • 因为两个链表可能长度不同,其中一个会先到达末尾 (nullptr)。
  • 直接将剩余的链表连接到合并链表的末尾,完成操作。

方法二:递归

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {// 如果其中一个链表为空,直接返回另一个链表if (list1 == nullptr) return list2;if (list2 == nullptr) return list1;// 比较当前节点的值,选择较小的节点作为当前结果if (list1->val <= list2->val) {list1->next = mergeTwoLists(list1->next, list2);return list1;} else {list2->next = mergeTwoLists(list1, list2->next);return list2;}}
};

递归逻辑

  • 比较 list1list2 当前节点的值:
    1. 如果 list1->val <= list2->val,说明 list1 的当前节点应出现在结果链表中:
      • 递归调用 mergeTwoLists 合并剩余的 list1->nextlist2
      • list1 的当前节点与递归返回的结果连接。
    2. 否则,list2 的当前节点应出现在结果链表中:
      • 递归调用 mergeTwoLists 合并 list1list2->next
      • list2 的当前节点与递归返回的结果连接。

返回结果

  • 每次递归都返回较小节点的指针,从而逐步构建合并后的链表。

方法三:原地修改迭代

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if (list1 == nullptr) return list2;if (list2 == nullptr) return list1;ListNode* head = (list1->val <= list2->val) ? list1 : list2;if (head == list1) list1 = list1->next;else list2 = list2->next;ListNode* current = head;while (list1 != nullptr && list2 != nullptr) {if (list1->val <= list2->val) {current->next = list1;list1 = list1->next;} else {current->next = list2;list2 = list2->next;}current = current->next;}current->next = (list1 != nullptr) ? list1 : list2;return head;}
};

  • 比较 list1list2 当前节点的值:
    • 如果 list1->val <= list2->val,将 list1 当前节点接到结果链表,并移动 list1
    • 否则,将 list2 当前节点接到结果链表,并移动 list2
  • 同时移动结果链表指针 current,保持末尾指向最新节点。
  • 循环结束时,至少有一个链表到达末尾 (nullptr)。
  • 直接将剩余的链表连接到结果链表末尾。
关键字:惠州双语网站建设费用_甘肃做网站_本地推广最有效的方法_优化外包哪里好

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: