前言关于链表，常见的算法题如下：单链表反转两个有序链表合并删除链表的最后n个节点找到的中间节点链表在检测链表环之前，我们讲了第一个问题——单链表的反转。今天来说说第二个问题：两个有序链表的合并。链表，合并两个链表，并保持新链表中的节点仍然按升序排列。例1：输入：1->2->4,1->3->4输出：1->1->2->3->4->4限制：0<=链表长度<=1000解1先分析题干：递增，链表，将两个递增链表合并为一个递增链表。那么我们很容易想到一种方式，两个指针分别遍历两个链表：比如两个链表分别是node1和node2，然后一个新的链表node3作为输出node1.val节点2.val。然后将node3指向node2，然后node2指针向下走一步，再和node1.val进行比较。什么时候结束？当一个node.next为null时，就意味着结束了。比如node1遍历后，直接将node3指向node2。publicListNodemergeTwoLists(ListNode1,ListNode2){//创建要输出的链表节点dum，以及类指针操作的节点curListNodedum=newListNode(0);ListNodecur=dum;//结束条件为其中一个节点为Emptywhile(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);returndum.next;}时间复杂度这个算法需要遍历两个不同长度的链表，所以时间复杂度是O(m+n)+n长度？那么空间复杂度也是O(m+n)？事实上，链表并不会单独创建额外的空间。我们其实只是新建了一个节点，然后把这个节点指向之前的一些节点空间地址，所以并没有额外占用m或者n大小的空间，只用到了dum和cur这两个节点的引用。所以这个解的空间复杂度是O(1)解2按照前面的格式，我们肯定会有第二个解😄。所以，我们需要好好想想。刚才的解有优化点吗？不能单独创建一个链表节点吗？其实我们可以发现，每一个操作都是类似的，比较大小，然后指定下一个节点。所以我们可以递归地写。下面介绍递归的两个要素：1.找出每次递归过程中需要的操作。也就是我们刚才说的重复操作。2.寻找递归终止的条件。那么根据这个思路，我们可以这样想：首先是每次递归过程中需要做的操作，写个伪代码：if(l1.val
