https://ansonznl.github.io/assets/js/v-069ec32f.14e56ad9.js

1"use strict";(self.webpackChunk=self.webpackChunk||[]).push([[6836],{9472:(n,s,a)=>{a.r(s),a.d(s,{data:()=>p});const p={key:"v-069ec32f",path:"/computer-base/LeetCode/%E5%90%88%E5%B9%B6%E4%B8%A4%E4%B8%AA%E6%9C%89%E5%BA%8F%E9%93%BE%E8%A1%A8.html",title:"",lang:"en-US",frontmatter:{},excerpt:"",headers:[{level:2,title:"描述",slug:"描述",children:[]},{level:2,title:"解法",slug:"解法",children:[{level:3,title:"递归",slug:"递归",children:[]},{level:3,title:"迭代",slug:"迭代",children:[]}]},{level:2,title:"总结",slug:"总结",children:[]}],filePathRelative:"computer-base/LeetCode/合并两个有序链表.md",git:{}}},3782:(n,s,a)=>{a.r(s),a.d(s,{default:()=>r});var p=a(6252);const e=(0,p.uE)('<h2 id="描述" tabindex="-1"><a class="header-anchor" href="#描述" aria-hidden="true">#</a> 描述</h2><p>将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。</p><p>示例 1：</p><div class="language-text ext-text line-numbers-mode"><pre class="language-text"><code>输入：l1 = [1,2,4], l2 = [1,3,4]\n输出：[1,1,2,3,4,4]\n</code></pre><div class="line-numbers"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p>示例 2：</p><div class="language-text ext-text line-numbers-mode"><pre class="language-text"><code>输入：l1 = [], l2 = []\n输出：[]\n</code></pre><div class="line-numbers"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p>示例 3：</p><div class="language-text ext-text line-numbers-mode"><pre class="language-text"><code>输入：l1 = [], l2 = [0]\n输出：[0]\n</code></pre><div class="line-numbers"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div>',8),t=(0,p.Uk)("题目链接："),l={href:"https://leetcode-cn.com/problems/merge-two-sorted-lists/",target:"_blank",rel:"noopener noreferrer"},o=(0,p.Uk)("合并两个有序链表"),c=(0,p.uE)('<h2 id="解法" tabindex="-1"><a class="header-anchor" href="#解法" aria-hidden="true">#</a> 解法</h2><h3 id="递归" tabindex="-1"><a class="header-anchor" href="#递归" aria-hidden="true">#</a> 递归</h3><p><strong>思路</strong> 分而治之， 自上而下的方式。 边界条件： 如果 l1 为 null， 则返回 l2， 说明， 反之。 递归条件：判断 l1 和 l2 头节点值得大小， 那个更小， 就把那个添加到上一个的前面。</p><div class="language-javascript ext-js line-numbers-mode"><pre class="language-javascript"><code><span class="token keyword">let</span> <span class="token function-variable function">mergeTwoLists</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">l1<span class="token punctuation">,</span> l2</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>\n  <span class="token keyword">if</span> <span class="token punctuation">(</span>l1 <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span> l2<span class="token punctuation">;</span>\n  <span class="token keyword">if</span> <span class="token punctuation">(</span>l2 <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span> l1<span class="token punctuation">;</span>\n  <span class="token keyword">if</span> <span class="token punctuation">(</span>l1<span class="token punctuation">.</span>val <span class="token operator">&lt;=</span> l2<span class="token punctuation">.</span>val<span class="token punctuation">)</span> <span class="token punctuation">{</span>\n    l1<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token function">mergeTwoLists</span><span class="token punctuation">(</span>l1<span class="token punctuation">.</span>next<span class="token punctuation">,</span> l2<span class="token punctuation">)</span><span class="token punctuation">;</span>\n    <span class="token keyword">return</span> l1<span class="token punctuation">;</span>\n  <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>\n    l2<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token function">mergeTwoLists</span><span class="token punctuation">(</span>l1<span class="token punctuation">,</span> l2<span class="token punctuation">.</span>next<span class="token punctuation">)</span><span class="token punctuation">;</span>\n    <span class="token keyword">return</span> l2<span class="token punctuation">;</span>\n  <span class="token punctuation">}</span>\n<span class="token punctuation">}</span><span class="token punctuation">;</span>\n</code></pre><div class="line-numbers"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br></div></div><p><strong>复杂度分析</strong></p><ul><li>时间复杂度：O(1)</li><li>空间复杂度：O(m+n)</li></ul><h3 id="迭代" tabindex="-1"><a class="header-anchor" href="#迭代" aria-hidden="true">

1#</a> 迭代</h3><p>当判断 l1 和 l2 都是 null 时，判断 l1 和 l2 的哪个头节点更小，然后将较小的节点添加到结果里，对应链表里应该移除当前节点然后后移一位。</p><p>思路： 1.新建一个空节点（headNode），然后维护一个 prev 指针，调整他的 next 指针。</p><ol start="2"><li>判断 l1 和 l2 的值大小，如果 l1 &lt; l2 就把 l1 当前的节点接到 prev 节点的后面，同时将 l1 的指针后移一位。否则，l2 也执行同样同样操作。</li><li>重复 2，直到 l1 或者 l2 为空后，将非空列表接在合并链表的后面，返回即可。</li></ol><div class="language-javascript ext-js line-numbers-mode"><pre class="language-javascript"><code><span class="token keyword">var</span> <span class="token function-variable function">mergeTwoLists</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">l1<span class="token punctuation">,</span> l2</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>\n  <span class="token keyword">let</span> mergedHead <span class="token operator">=</span> <span class="token punctuation">{</span>\n    val<span class="token operator">:</span> <span class="token string">&quot;&quot;</span><span class="token punctuation">,</span>\n    next<span class="token operator">:</span> <span class="token keyword">null</span><span class="token punctuation">,</span>\n  <span class="token punctuation">}</span><span class="token punctuation">;</span>\n  <span class="token keyword">let</span> crt <span class="token operator">=</span> mergedHead<span class="token punctuation">;</span> <span class="token comment">// 活动指针</span>\n  <span class="token keyword">while</span> <span class="token punctuation">(</span>l1 <span class="token operator">&amp;&amp;</span> l2<span class="token punctuation">)</span> <span class="token punctuation">{</span>\n    <span class="token keyword">if</span> <span class="token punctuation">(</span>l1<span class="token punctuation">.</span>val <span class="token operator">&gt;</span> l2<span class="token punctuation">.</span>val<span class="token punctuation">)</span> <span class="token punctuation">{</span>\n      crt<span class="token punctuation">.</span>next <span class="token operator">=</span> l2<span class="token punctuation">;</span> <span class="token comment">// 拿出小值往前排</span>\n      l2 <span class="token operator">=</span> l2<span class="token punctuation">.</span>next<span class="token punctuation">;</span> <span class="token comment">// 将 l2 重新赋值，相当于了删除了一个节点</span>\n    <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>\n      crt<span class="token punctuation">.</span>next <span class="token operator">=</span> l1<span class="token punctuation">;</span> <span class="token comment">//</span>\n      l1 <span class="token operator">=</span> l1<span class="token punctuation">.</span>next<span class="token punctuation">;</span>\n    <span class="token punctuation">}</span>\n    crt <span class="token operator">=</span> crt<span class="token punctuation">.</span>next<span class="token punctuation">;</span> <span class="token comment">// 相等的情况</span>\n  <span class="token punctuation">}</span>\n  crt<span class="token punctuation">.</span>next <span class="token operator">=</span> l1 <span class="token operator">||</span> l2<span class="token punctuation">;</span>\n  <span class="token keyword">return</span> mergedHead<span class="token punctuation">.</span>next<span class="token punctuation">;</span>\n<span class="token punctuation">}</span><span class="token punctuation">;</span>\n</code></pre><div class="line-numbers"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br></div></div><p><strong>复杂度分析</strong></p><ul><li>时间复杂度：O(n)</li><li>空间复杂度：O(1)</li></ul><h2 id="总结" tabindex="-1"><a class="header-anchor" href="#总结" aria-hidden="true">

1#</a> 总结</h2><p>总感觉 JS 实现的链表怪怪的，打印出来一堆对象套对象。</p><p>这一节涉及的知识挺多的，链表、递归。</p>',16),r={render:function(n,s){const a=(0,p.up)("OutboundLink");return(0,p.wg)(),(0,p.iD)(p.HY,null,[e,(0,p._)("p",null,[t,(0,p._)("a",l,[o,(0,p.Wm)(a)])]),c],64)}}}}]);