上海建设厅网站,那些网站可以做自媒体,做婚礼邀请函网站,学做网站根学ps有前途吗题目#xff1a;
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1#xff1a; 输入#xff1a;l1 [1,2,4], l2 [1,3,4]
输出#xff1a;[1,1,2,3,4,4]示例 2#xff1a;
输入#xff1a;l1 [], l2 []
输…题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 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 均按 非递减顺序 排列 解决
解法1循环双指针
用示例一来演示引入结果节点P对l1和l2的头节点进行比较11优先把l2的节点挂到结果中l2指针后移。再比较l1的1和l2的313则把l1的节点挂到结果中l1指针后移。23则把l1的2挂到结果中l1指针后移。43则把l2的3挂到结果中l2指针后移。44把l2的节点挂到结果中l2指针后移这时候l2的指针已经到末尾了已经null了则把l1的剩下的链表节点都挂到结果链表中这样就得到了合并的链表。
用红色来表示l1的节点则新链表为1-1-2-3-4-4
时间复杂度为O(mn).因为两个链表都要遍历一遍m和n分别为链表的元素个数。
空间复杂度为O(1).
/*** 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) {if(list1null)//边界情况return list2;if(list2null)//边界情况return list1;ListNode resultNodenew ListNode(0);ListNode presultNode;//结果节点while(list1!nulllist2!null){//比较if(list1.vallist2.val){//l1节点的值小则把l1节点挂结果中p.nextlist1;list1list1.next;}else{p.nextlist2;list2list2.next;}pp.next;}if(list1!null){//其中一个链表指针遍历到末尾之后看哪个链表还没遍历完若是l1没遍历完则把l1剩下的挂在结果中p.nextlist1;}if(list2!null){p.nextlist2;//把l2没遍历完的挂在结果中}return resultNode.next;}
}
在IDEA上运行用的完整代码
class ListNode{int val;ListNode next;ListNode(int val){this.valval;}public void add(int newval){ListNode newNodenew ListNode(newval);if(this.nextnull){this.nextnewNode;}elsethis.next.add(newval);}public void print(){System.out.print(this.val);if(this.next!null){System.out.print(-);this.next.print();}}
}
public class leetcode5 {/*循环双指针解决*/static ListNode mergeTwoLists(ListNode l1,ListNode l2){if(l1null)return l2;if(l2null)return l1;ListNode resultNodenew ListNode(0);ListNode presultNode;while(l1!nulll2!null){if(l1.vall2.val){p.nextl1;l1l1.next;}else{p.nextl2;l2l2.next;}pp.next;}if(l1!null){p.nextl1;}if(l2!null){p.nextl2;}return resultNode.next;}public static void main(String[] args) {ListNode l1new ListNode(1);l1.add(2);l1.add(4);l1.print();System.out.println();ListNode l2new ListNode(1);l2.add(3);l2.add(4);l2.print();System.out.println();mergeTwoLists(l1,l2).print();System.out.println();System.out.println(hello list);/*1-2-41-3-41-1-2-3-4-4hello list */}
}解法2递归
还是以示例一来演示本来l1是1-2-4。l2是1-3-4。就是这两个链表要合并。然后如果把l2的1合并到l1之后就相当于是新l11-1-2-4和l23-4要合并。所以可以用递归来解决。
时间复杂度为O(mn)
空间复杂度为O(mn)
/*** 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) {if(list1null)return list2;if(list2null)return list1;if(list1.vallist2.val){list1.nextmergeTwoLists(list1.next,list2);return list1;}list2.nextmergeTwoLists(list1,list2.next);return list2;}
}
在IDEA上运行用的完整代码
class ListNode{int val;ListNode next;ListNode(int val){this.valval;}public void add(int newval){ListNode newNodenew ListNode(newval);if(this.nextnull){this.nextnewNode;}elsethis.next.add(newval);}public void print(){System.out.print(this.val);if(this.next!null){System.out.print(-);this.next.print();}}
}
public class leetcode5 {/*递归解决*/static ListNode mergeTwoLists2(ListNode l1,ListNode l2){if(l1null)return l2;if(l2null)return l1;if(l1.vall2.val){l1.nextmergeTwoLists2(l1.next,l2);return l1;}l2.nextmergeTwoLists2(l1,l2.next);System.out.print(-);System.out.print(l2.val);return l2;}public static void main(String[] args) {ListNode l1new ListNode(1);l1.add(2);l1.add(4);l1.print();System.out.println();ListNode l2new ListNode(1);l2.add(3);l2.add(4);l2.print();System.out.println();System.out.println(hello list);System.out.println(下面的链表要倒着看);mergeTwoLists2(l1,l2);/*1-2-41-3-4hello list下面的链表要倒着看-4-4-3-2-1-1*/}
}加油加油^_^
