剑指offer-16、合并两个有序链表
<h2 id="题描述">题⽬描述</h2><p>输⼊两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满⾜单调不减规则。</p>
<p>如输⼊{1,3,5} , {2,4,6} 时，合并后的链表为{1,2,3,4,5,6} ，所以对应的输出为{1,2,3,4,5,6} ，转换过程如下图所示：</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503231847572.png" alt="" loading="lazy"></p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="迭代法双指针">迭代法（双指针）</h3>
<p>使用两个指针分别遍历两个链表，比较当前节点的值，将较小的节点连接到结果链表上。当一个链表遍历完后，将另一个链表的剩余部分直接连接到最后。</p>
<pre><code class="language-java">public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 创建哑节点作为合并后链表的头节点前驱
ListNode dummy = new ListNode(-1);
ListNode current = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
// 连接剩余部分
current.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n+m)，n和m分别是两个链表的长度</li>
<li><strong>空间复杂度</strong>：O(1)，只使用了固定数量的指针</li>
</ul>
<h3 id="递归比较">递归比较</h3>
<p>利用递归将问题分解：每次比较两个链表的头节点，选择较小的节点作为合并后链表的头节点，然后递归地合并剩余部分。</p>
<pre><code class="language-java">public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val <= l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n+m)，每个节点都会被访问一次</li>
<li><strong>空间复杂度</strong>：O(n+m)，递归调用栈的深度</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19001420 看到楼主的分享了！这是经典的双指针合并问题，讲解得很清晰呢~
两种方法都写得很棒：
迭代法使用哑节点确实让代码简洁不少，不需要额外处理头节点的情况。我之前写的时候经常忘记创建哑节点，导致在处理第一个节点时要单独讨论，特别麻烦。
递归法虽然代码更简洁，但要注意递归深度的问题。如果链表很长的话，可能会导致栈溢出，这时候迭代法就更稳妥一些。
另外补充一个小细节：如果链表节点数量很大，递归法会占用O(n+m)的栈空间，而迭代法只需要O(1)的空间，在实际面试中如果面试官问到空间复杂度，可以提一下这个区别。
总的来说这两种解法都很值得掌握，迭代法偏实用，递归法偏技巧，面试的时候根据情况选择就好啦~
感谢楼主的整理，代码格式也很清晰，收藏了！smile
頁:
[1]