一、题目描述
来源:力扣(LeetCode)
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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 均按 非递减顺序 排列
二丶思路分析
双指针解法
这道题类似 【刷题记录】2. 两数相加 在上题中,是给出两个链表,对节点中的数字依次相加,合成一个新的链表,而在此题中,则是直接比较(因为l1 和 l2 均按 非递减顺序 排列
)两个链表中节点的值,合成一个新的链表即可。
三、代码实现
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(-1); ListNode prev = dummy; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { prev.next = l1; l1 = l1.next; } else { prev.next = l2; l2 = l2.next; } prev = prev.next; } // 如果存在链表还没遍历完 prev.next = l1 == null ? l2 : l1; return dummy.next; } }
复杂度分析
- 时间复杂度:对两条链表扫描一遍。复杂度为
网络异常,图片无法展示|
m
,n
为两个链表的长度 - 空间复杂度:
网络异常,图片无法展示|
运行结果
网络异常,图片无法展示
|
总结
这道题目也是一个通过双指针对链表进行处理的一个变形题目。理解这种思路,我们可以在很多地方利用这个来帮助我们处理相应的问题。
继续加油~