将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
image.png
示例 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 均按 非递减顺序 排列
代码实现:
public class shuzu {
public static void main(String[] args) {
ListNode node1=new ListNode(1);
ListNode node2=new ListNode(2);
ListNode node3=new ListNode(3);
ListNode node4=new ListNode(4);
ListNode node5=new ListNode(5);
node1.next = node3;
node3.next = node5;
node2.next = node4;
// ListNode node= mergeTwoLists(node1,node2);
ListNode node=mergeTwoListstwo(node1,node2);
while (node!=null){
System.out.print("----"+node.val);
node=node.next;
}
}
/**方法1:
* 迭代法
* 1.设置一个哨兵结点(假结点)pHead，用于作为返回最终结果链表的头指针；
* 2.设置一个游标p,随着链表结点的增加移动，初始情况下，p指向pHead；
* 3.在l1、l2均未达到链表结尾(null)前提下循环迭代。
* l1当前指向结点的值小于等于l2当前指向结点的值时，p.next指向l1，l1移向下个结点，否则，p.next指向l2，l2移向下个结点；游标p移向下个结点。
* 4.由于当循环结束时,l1、l2中有一个仍然非空，所以直接将剩余结点添加。
* 时间复杂度：O(N+M)，N和M分别为两个有序链表的长度，循环次数不会超过两个长度之和，其他操作的时间复杂度都是常数级别的；
* 空间复杂度：O(1)，只需要常数的空间存放若干个变量。
* */
public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//创建新链表， prehead 用于记录头结点,也称为哨兵节点
ListNode prehead = new ListNode(-1);
ListNode prev = prehead;//游标
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;
}
// 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
//其实就是说明有一个链表已经连结完成，将l1、l2中剩余的结点直接连接在 prehead 之后
prev.next = l1 == null ? l2 : l1;
//返回时跳过头结点
return prehead.next;
}
static class ListNode{
int val;
ListNode next;
ListNode() {}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
//方法2:递归 递归终止的条件是1或者2为空
//如果l1.val < l2.val的话，表头就是l1的头结点，否则是l2的头结点;
//递归的内容是得到的两个链表中小的结点后，在剩下的结点中找下一个小的结点
/*时间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。因为每次调用递归都会去掉
l1 或者 l2 的头节点(直到至少有一个链表为空)，
函数 mergeTwoList 至多只会递归调用每个节点一次。因此，时间复杂度取决于合并后的链表长度，
即 O(n+m)。
空间复杂度：O(n+m)，递归就是程序内部维护了一个栈,每次将最小值压栈，也就是用一个栈来维护顺序。*/
public static ListNode mergeTwoListstwo(ListNode l1, ListNode l2) {
//若有一条链表为空，则返回另一条链表
if(l1==null){
return l2;
}
if(l2==null){
return l1;
}
//递归调用
if(l1.val<l2.val){
l1.next=mergeTwoListstwo(l1.next,l2);
return l1;
}else{
l2.next=mergeTwoListstwo(l1,l2.next);
return l2;
}
}
}
网友评论