网站按关键词显示广告图片,义乌网站建设和制作,一个网站应该怎么做,咸阳网站开发公司地址题目描述
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1#xff1a; 输入#xff1a;l1 [1,2,4], l2 [1,3,4]
输出#xff1a;[1,1,2,3,4,4]示例 2#xff1a;
输入#xff1a;l1 [],…题目描述
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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 100l1 和 l2 均按 非递减顺序 排列
解法
思路依次从两个链表中取元素比较大小小的那个加到新链表
java代码
/*** 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 list1, ListNode list2) {// 哑节点ListNode dummy new ListNode(0, null);// 当前节点ListNode cur dummy;while (list1 ! null || list2 ! null) {// 取链表当前的值如果节点为空设为Integer.MAX_VALUE即可int val1 list1 null ? Integer.MAX_VALUE : list1.val;int val2 list2 null ? Integer.MAX_VALUE : list2.val;// 比较节点值小的那个加到下个节点去并移动到下个节点if (val1 val2) {cur.next new ListNode(val1, null);list1 list1.next;} else {cur.next new ListNode(val2, null);list2 list2.next;}cur cur.next;}return dummy.next;}
}复杂度
时间复杂度O(nm)其中 n 和 m 分别为两个链表的长度空间复杂度O(n m)
