前言
大家好，我是「程序员小熊」。今天给大家带来一道「链表」相关的题目，这道题同时也是字节、腾讯、亚马逊和微软等大厂的面试题，即力扣上的第 21 题-合并两个有序链表。
本文主要介绍「递归」和「迭代」两种策略来解答此题，供大家参考，希望对大家有所帮助。
合并两个有序链表
解题思路
要想将两个「升序」链表合并成一个新的「升序」链表，比较容易想到通过「递归」去实现。
方法一：递归
采用递归的「主要思路」
假设链表分别为 A 和 B，先比较 A 和 B 的头节点的值的大小，选择头节点值较小者（假设为 A）作为新的链表的头节点；然后再比较 A 的第二个节点的值与 B 的头节点的值的大小关系，选择较小者作为新链表的第二个节点；依次类推找出新链表的第三个节点...
❝ 递归终止条件：两链表一个为空时，结束递归。
❞
Show me the Code
「C」
「C++」
「Java」
「Python3」
「Golang」
「复杂度分析」
时间复杂度：「O(n + m)」，其中 n 和 m 分别为两个链表的长度，需要递归调用两个链表的每个节点一次。
空间复杂度：「O(n + m)」。
方法二：迭代
除了采用递归外，还可以采用迭代的方法，具体如何操作，如下例子所示：
「举例」
以链表 l1：1->4->null 和链表 l2：2->3->null 为例。
设置两个指针 cur1 和 cur2，分别指向两个链表的头节点；
比较 cur1 和 cur2 指向的节点的值的大小，右移指向的节点值较小的 cur1；
设置一个指针 pre1，记录上次比较时值较小的节点；
设置一个指针 next，记录 cur2 指向节点的下一节点；
由于 pre1 指向的节点值小于 cur2 指向的节点值，连接它们；
同时由于 cur2 指向的节点小于 cur1 指向的节点，连接它们；
右移 pre1 和 cur2 分别到 cur2 和 next 位置；
由于 cur1 指向的节点值大于 cur2 指向的节点值，将 pre1 指向的节点连接 cur2 指向的节点；
由于 cur2 指向的节点值小于 cur1 指向的节点值，连接它们；
采用迭代法，合并两个上升链表到一个的完整过程，如下动图示：
Show me the Code
「C」
「C++」
「Java」
「复杂度分析」
时间复杂度：「O(n + m)」，其中 n 和 m 分别为两个链表的长度，需要遍历两个链表的每个节点。
空间复杂度：「O(1)」，未开辟额外空间。
链表往期精彩回顾
更多精彩
关注公众号「程序员小熊」