前言
关于链表,常见的算法问题有以下几种:
之前我们说过了第一个问题——单链表反转
,今天说说第二个问题:两个有序的链表合并
输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
限制:
0 <= 链表长度 <= 1000
先分析题干:递增,链表,合并
两个递增的链表,合并成一个递增的链表。
那么我们很容易想到一个方法就是,两个指针分别遍历两个链表:
比如两个链表是node1、node2
,然后一个新链表node3
作为输出
node1.val< node2.val
。那么就把node3指向node1,然后node1指针向下走一步,再和node2.val相比较。node1.val> node2.val
。那么就把node3指向node2,然后node2指针向下走一步,再和node1.val相比较。什么时候结束呢?当某个node.next为null的时候,就代表结束了。
比如node1遍历结束,就把node3直接指向node2。
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//创建要输出的链表结点dum,和一个用于类指针操作的结点cur
ListNode dum = new ListNode(0);
ListNode cur = dum;
//结束条件是当其中一个结点为空
while(l1 !=null && l2 != null){
//当链表1的结点小的时候,就把cur指向这个结点,并且链表1下移到下个结点
if(l1.val <= l2.val){
cur.next=l1;
l1=l1.next;
}else {
cur.next=l2;
l2=l2.next;
}
cur=cur.next;
}
cur.next = (l1 == null? l2 : l1);
return dum.next;
}
这个算法要遍历两个不同长度的链表,所以时间复杂度为O(m+n)
关于空间复杂度,有可能有的朋友会觉得用到了m+n长度的链表?所以空间复杂度也是O(m+n)
?
其实不然,链表并不会单独创建额外的空间,我们其实只是新建了一个结点,然后将这个结点指向之前已经有的结点空间地址
,所以并没有占用额外的m或者n大小的空间,只用到了dum和cur两个结点的引用。
所以该解法的空间复杂度为O(1)
按照之前的格式,我们肯定会有第二种解法?。
所以、我们需要想想,刚才的解法还有优化点
吗?
是否可以不单独创建链表结点呢?
其实可以发现我们每次操作都是类似的,都是比较大小,然后指定next结点
。
所以我们可以写成递归的写法。
这里说下递归的两个要素
:
那按照这个思路,我们就可以想想了:
每一次
递归过程中需要做的操作,写段伪代码: if (l1.val<l2.val) {
l1.next;
return l1;
}else {
l2.next;
return l2;
}
终止条件
,也就是我们在解法一中类似的条件,当某个链表便利结束,结点为空的时候。 if (l1 == null ) {
return l2;
}
if (l2 == null ) {
return l1;
}
那么结合这两个递归要素
,我们就可以写出一个递归解法:
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null || l2 == null)
return l1 == null ? l2 : l1;
if(l1.val<l2.val)
{
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
else
{
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
还是很奇妙
的吧~都没有用到单独的结点引用。
我们可以这样理解,有点像我们直接操作现实中的两个链表,去给他们按顺序进行了一个连线:
时间复杂度还是会走完两个链表的每一个结点,所以还是O(m+n)
都没有用到单独的空间,所以空间复杂度也是O(1)
https://time.geekbang.org/column/article/41149
https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/