【LeetCode】合併兩個有序連結串列 - 遞迴 - 迭代

語言: CN / TW / HK

theme: cyanosis highlight: a11y-dark


小知識,大挑戰!本文正在參與“程式設計師必備小知識”創作活動。

嗨!~ 大家好,我是YK菌 🐷 ,一個微系前端 ✨,喜歡分享自己學到的小知識 🏹,歡迎關注我呀 😘 ~ [微訊號: yk2012yk2012,微信公眾號:ykyk2012]

今天來合併兩個有序連結串列,這道題我在 [浦發銀行筆試] 中遇到過

21. 合併兩個有序連結串列

將兩個升序連結串列合併為一個新的 升序 連結串列並返回。新連結串列是通過拼接給定的兩個連結串列的所有節點組成的。

連結: https://leetcode-cn.com/problems/merge-two-sorted-lists/

示例

image.png

輸入: l1 = [1,2,4], l2 = [1,3,4] 輸出: [1,1,2,3,4,4]

【解法一】迭代 - 非遞迴

我們先使用一種簡單好理解的解法,就是迭代解法,首先這兩個連結串列都是有序的,所以可以將直接判斷 l1 和 l2 哪一個連結串列的頭節點的值更小,將較小值的節點新增到結果裡,當一個節點被新增到結果裡之後,將對應連結串列中的節點向後移一位。

```javascript /* * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } /

/* * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} / var mergeTwoLists = function (l1, l2) { // 建立一個頭節點,值為 -1 const prehead = new ListNode(-1); // 定義一個前指標,開始的時候指向頭節點 let prev = prehead; // 只要兩個連結串列都沒有遍歷完,就一直遍歷 while (l1 !== null && l2 !== null) { if (l1.val <= l2.val) { prev.next = l1; l1 = l1.next; } else { prev.next = l2; l2 = l2.next; } // 前指標後移 prev = prev.next; }

// 退出迴圈一定是因為某一個連結串列已經遍歷完了,只需要把另一個連結串列的剩餘部分都接到prev後面即可 if (l1 === null) { prev.next = l2; } else{ prev.next = l1; }

// 直接返回頭節點之後的連結串列 return prehead.next; }; ```

image.png

【解法二】遞迴

接下來我們再實現一種遞迴的解法

首先找到遞迴終止條件出口,就是一個連結串列為空,直接返回另一個連結串列

javascript if(l1 === null){ return l2 }else if(l2 === null){ return l1 } 然後進行一般的判斷

判斷兩個連結串列的頭節點哪一個更小,更小的那個頭節點保留,然後遞迴呼叫剩餘的兩個連結串列

javascript if(l1.val < l2.val){ l1.next = mergeTwoLists(l1.next, l2) return l1 } 可以看下面這個動圖來理解一下

在這裡插入圖片描述

javascript /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */ var mergeTwoLists = function(l1, l2) { if(l1 === null){ return l2 }else if(l2 === null){ return l1 }else if(l1.val < l2.val){ l1.next = mergeTwoLists(l1.next, l2) return l1; }else{ l2.next = mergeTwoLists(l1, l2.next) return l2 } };

image.png

「其他文章」