中国空间站拒绝10国名单,网站建设属于现代服务吗,网站建设发生的成本如何记账,企业邮箱模板文章目录 题目描述解题方法双指针遍历java代码 题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1#xff1a;
输入#xff1a;l1 [1,2,4], l2 [1,3,4]
输出#xff1a;[1,1,2,3,4,4]示例 2#xff… 文章目录 题目描述解题方法双指针遍历java代码 题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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 均按 非递减顺序 排列
解题方法
双指针遍历
为了方便返回链表后的头结点我们设置一个哑结点dummyNode)哑结点的next指针指向升序链表的头结点。
已知两个链表都是升序链表我们初始设置指针p指向哑结点指针l1和l2分别指向两个链表的头结点此时最小的元素必然在l1.val和l2.val之间若最小元素是l1.val则将p的next指针指向l1的结点p也重新指向l1的结点l1指针指向l1.next的结点若最小元素是l2.val则将p的next指针指向l2的结点p也重新指向l2的结点l2指针指向l2.next的结点。下一个最小的元素也必然在l1.val和l2.val之间还是按照上面的方法让l1和l2的指针不断往后遍历。直到l1或者l2遍历到末尾时p的next指针指向l1和l2之中还没有遍历到末尾的指针。此时返回哑结点的next结点即为升序链表的头结点。
java代码
ListNode结构
public class ListNode {public int val;public ListNode next;public ListNode() {}public ListNode(int val) {this.val val;}public ListNode(int val, ListNode next) {this.val val;this.next next;}
}链表合并方法
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode dummyNode new ListNode(0, null);ListNode p dummyNode;ListNode l1 list1;ListNode l2 list2;while (l1 ! null l2 ! null) {if (l1.val l2.val) {p.next l1;p p.next;l1 l1.next;} else {p.next l2;p p.next;l2 l2.next;}}if (l1 ! null) {p.next l1;} else {p.next l2;}return dummyNode.next;
}时间复杂度 O ( M N ) O(MN) O(MN) M M M和 N N N为两个链表的长度 空间复杂度 O ( 1 ) O(1) O(1) 个人公众号 个人小游戏
