将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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 均按 非递减顺序 排列
/** * 思路: * 新建一个节点作为前驱节点,指向新的链表 * 比较list1和list2的值,新链表的next指向小的那个节点,移动节点 * 当list1用完后指向list2 * 当list2用完,反之 */ public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode pre = new ListNode(0); ListNode curr = pre; while (true){ if (list1==null){ curr.next=list2; break; }else if (list2==null){ curr.next=list1; break; } if (list1.val<list2.val){ ListNode next = list1.next; curr.next=list1; curr=list1; list1=next; }else { ListNode next = list2.next; curr.next=list2; curr=list2; list2=next; } } return pre.next; }
时间复杂度:On
空间复杂度:O1
/** * 思路: * 第一次进入函数:判断list1和list2当前节点谁的值小,作为头节点 * 递归的去找下一个节点 * 当list1用完后直接返回list2 * 当list2用完,反之 */ public ListNode mergeTwoLists(ListNode list1, ListNode list2) { if (list1==null){ return list2; } if (list2==null){ return list1; } if (list1.val>list2.val){ list2.next=mergeTwoLists(list1,list2.next); return list2; }else { list1.next=mergeTwoLists(list1.next,list2); return list1; } }
时间复杂度:On
空间复杂度:On