库存管理软件单机版_软件定制开发推荐_网站底部友情链接代码_营销排名seo

💢欢迎来到张胤尘的技术站
💥技术如江河，汇聚众志成。代码似星辰，照亮行征程。开源精神长，传承永不忘。携手共前行，未来更辉煌💥

官方站点： 力扣 Leetcode

算法每日一练 (2)

合并两个有序链表

题目地址：合并两个有序链表

题目描述

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

示例1：

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

示例2：

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

示例3：

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

提示：

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

解题思路

• 首先确定边界条件，根据题目要求合并两个升序的链表，最终结果也是一个升序的链表，那么有如下两个情况：
  • 两个链表都是空的，直接返回空即可，不需要做其他任何的操作。
  • 当其中某一个链表是空的，可以直接返回另外一个已经升序的链表，不需要做其他任何的操作。
• 创建一个最终结果的头节点指针 h，由于两个链表都是升序，那么两个链表的头节点一定是该链表中值最小的节点，因此只需要确定两个链表中哪个头节点是最小的，只要让 h 指向即可，最终返回的结果也是返回 h 头节点指针。
• 然后借助三个临时指针变量 t、 i 和 j：
  • t：辅助指针变量，用于连接 i 指针变量和 j 指针变量中指向的最小的节点。
  • i：用于遍历链表的辅助指针变量，初始化指向 h 的下个节点。
  • j：用于遍历链表的辅助指针变量，初始化指向另外一个链表的头节点。
• 借助循环判断 i 和 j 指向的节点的最小值，然后使 t 的 next 指向最小节点（指针的移动）。
• 当不满足循环判断条件时只会出现如下两种情况：
  • 两个链表都已经遍历完毕，那么就可以直接结束程序。
  • 其中的一个链表遍历完毕，另外一个链表中还存在节点未遍历到；由于两个链表都已经是升序排列，那么剩下的一个链表也无需继续遍历，只需要让 t 的下一个节点的指针直接指向未遍历的节点。
• 最后，只需要返回头节点指针 h 即可。

解题代码

c/c++

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 && !list2)return nullptr;else if (!list1)return list2;else if (!list2)return list1;ListNode *h, *i, *j, *t;if (list1->val >= list2->val){h = list2;j = list1;}else{h = list1;j = list2;}i = h->next;t = h;while (i && j){if (i->val >= j->val){t->next = j;j = j->next;}else{t->next = i;i = i->next;}t = t->next;}if (!i && !j)return h;else if (!i)t->next = j;elset->next = i;return h;}
};

golang

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {if list1 == nil && list2 == nil {return nil} else if list1 == nil {return list2} else if list2 == nil {return list1}var h, i, j, t *ListNodeif list1.Val <= list2.Val {h = list1j = list2} else {h = list2j = list1}i = h.Nextt = hfor i != nil && j != nil {if i.Val <= j.Val {t.Next = ii = i.Next} else {t.Next = jj = j.Next}t = t.Next}if i == nil && j == nil {return h} else if i == nil {t.Next = j} else {t.Next = i}return h
}

lua

local ListNode = {}function ListNode:new(val, next)local obj = {}setmetatable(obj, self)self.__index = selfobj.Val = val or 0obj.Next = next or nilreturn obj
endlocal function mergeTwoLists(list1, list2)if list1 == nil and list2 == nil thenreturn nilelseif list1 == nil thenreturn list2elseif list2 == nil thenreturn list1endlocal h, i, j, tif list1.Val <= list2.Val thenh = list1j = list2elseh = list2j = list1endi = h.Nextt = hwhile i ~= nil and j ~= nil doif i.Val <= j.Val thent.Next = ii = i.Nextelset.Next = jj = j.Nextendt = t.Nextendif i == nil and j == nil thenreturn helseif i == nil thent.Next = jelset.Next = iendreturn h
end

🌺🌺🌺撒花！

如果本文对你有帮助，就点关注或者留个👍
如果您有任何技术问题或者需要更多其他的内容，请随时向我提问。