LeetCode题解之两个有序链表合并

前言

关于链表，题解常见的序链算法问题有以下几种：

单链表反转 两个有序的链表合并 删除链表倒数第n个结点 求链表的中间结点 链表中环的检测

之前我们说过了第一个问题——单链表反转，今天说说第二个问题：两个有序的表合并链表合并

题目：两个有序的链表合并

输入两个递增排序的链表，合并这两个链表并使新链表中的题解节点仍然是递增排序的。

示例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结点。

所以我们可以写成递归的写法。

这里说下递归的两个要素：

1、找到每一次递归过程中需要的操作。也就是我们刚才说的重复操作。

2、找到递归终止的条件。

那按照这个思路，我们就可以想想了：

首先，是每一次递归过程中需要做的操作，写段伪代码： 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/

本文转载自微信公众号「码上积木」，可以通过以下二维码关注。转载本文请联系码上积木公众号。