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

合并两个有序链表

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

输入：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;}}
};

递归逻辑

• 比较 list1 和 list2 当前节点的值：
  1. 如果 list1->val <= list2->val，说明 list1 的当前节点应出现在结果链表中：
     • 递归调用 mergeTwoLists 合并剩余的 list1->next 和 list2。
     • 将 list1 的当前节点与递归返回的结果连接。
  2. 否则，list2 的当前节点应出现在结果链表中：
     • 递归调用 mergeTwoLists 合并 list1 和 list2->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;}
};

• 比较 list1 和 list2 当前节点的值：
  • 如果 list1->val <= list2->val，将 list1 当前节点接到结果链表，并移动 list1。
  • 否则，将 list2 当前节点接到结果链表，并移动 list2。
• 同时移动结果链表指针 current，保持末尾指向最新节点。

• 循环结束时，至少有一个链表到达末尾 (nullptr)。
• 直接将剩余的链表连接到结果链表末尾。