LeetCode 21. 合併兩個有序鏈表

来源:https://www.cnblogs.com/izhoujie/archive/2020/05/22/12939879.html

我的LeetCode:https://leetcode cn.com/u/ituring/ 我的LeetCode刷題源碼[GitHub]:https://github.com/izhoujie/Algorithmcii LeetCode 21. 合併兩個有序鏈表 題目 將兩個升序鏈表合併為一個新的升 ...


我的LeetCode:https://leetcode-cn.com/u/ituring/

我的LeetCode刷題源碼[GitHub]:https://github.com/izhoujie/Algorithmcii

LeetCode 21. 合併兩個有序鏈表

題目

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

示例:

輸入:1->2->4, 1->3->4
輸出:1->1->2->3->4->4

來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/merge-two-sorted-lists
著作權歸領扣網路所有。商業轉載請聯繫官方授權,非商業轉載請註明出處。

解題思路

思路1-迭代

註意保留頭結點用以返回;

演算法複雜度: n為兩個鏈表的總長

  • 時間複雜度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
  • 空間複雜度: $ {\color{Magenta}{\Omicron\left(1\right)}} $

思路2-遞歸

遞歸代碼比較簡短;

演算法複雜度: n為兩個鏈表的總長

  • 時間複雜度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
  • 空間複雜度: $ {\color{Magenta}{\Omicron\left(n\right)}} $

演算法源碼示例

package leetcode;

/**
 * @author ZhouJie
 * @date 2020年1月6日 下午11:40:27 
 * @Description: 21. 合併兩個有序鏈表
 *
 */
public class LeetCode_0021 {

}

// Definition for singly-linked list.
class ListNode_0021 {
	int val;
	ListNode_0021 next;

	ListNode_0021(int x) {
		val = x;
	}
}

class Solution_0021 {
	/**
	 * @author: ZhouJie
	 * @date: 2020年5月22日 下午9:30:41 
	 * @param: @param l1
	 * @param: @param l2
	 * @param: @return
	 * @return: ListNode_0021
	 * @Description: 1-迭代;
	 *
	 */
	public ListNode_0021 mergeTwoLists_1(ListNode_0021 l1, ListNode_0021 l2) {
		if (l1 == null || l2 == null) {
			return l1 == null ? l2 : l1;
		}
		ListNode_0021 dummy = new ListNode_0021(0);
		ListNode_0021 node = dummy;
		while (l1 != null && l2 != null) {
			if (l1.val < l2.val) {
				dummy.next = l1;
				dummy = l1;
				l1 = l1.next;
			} else {
				dummy.next = l2;
				dummy = l2;
				l2 = l2.next;
			}
		}
		dummy.next = l1 == null ? l2 : l1;
		return node.next;
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年5月22日 下午9:30:51 
	 * @param: @param l1
	 * @param: @param l2
	 * @param: @return
	 * @return: ListNode_0021
	 * @Description: 2-遞歸;
	 *
	 */
	public ListNode_0021 mergeTwoLists_2(ListNode_0021 l1, ListNode_0021 l2) {
		if (l1 == null) {
			return l2;
		} else if (l2 == null) {
			return l1;
		} else if (l1.val < l2.val) {
			l1.next = mergeTwoLists_2(l1.next, l2);
			return l1;
		} else {
			l2.next = mergeTwoLists_2(l1, l2.next);
			return l2;
		}
	}
}


您的分享是我們最大的動力!

更多相關文章
  • [TOC] QuantLib 金融計算——案例之普通利率互換分析(2) 概述 QuantLib 中涉及利率互換的功能大致分為兩大類: 對存續的利率互換合約估值; 根據利率互換合約的成交報價推算隱含的期限結構。 這兩類功能是緊密聯繫的,根據最新報價推算出的期限結構通常可以用來對存續合約進行估值。 本文 ...
  • 1 緩存導致的可見性問題 一個線程對共用變數的修改,另一個線程可以立即看到,這稱之為可見性。 Java記憶體模型規定所有的變數存儲在主記憶體中。每個線程都有自己的工作記憶體,線程在工作記憶體中保存了使用到的主記憶體中變數的副本拷貝,線程對變數的操作必須在工作記憶體中進行,不能直接讀寫主記憶體中的變數。不同線程之間 ...
  • 在項目中經常遇到需要動態編輯特定事物的一組屬性,這時就涉及到新選擇的值與舊值對比更新,記錄在項目中採用的一種方法,主要採用 PHP array_filter() 函數: $delete_array = $add_new_array = array(); $array1 = array( array( ...
  • 檢測是否存在JDK 接下來可以將 開頭的安裝包均卸載即可 下載JDK 在 /opt/soft 內下載jdk "AdoptOpenJDK" 解壓完之後, /opt/module/ ⽬錄中會出現⼀個 的⽬錄 配置JDK環境變數 編輯 ⽂件,在⽂件尾部加⼊如下 JDK 環境配置即可 然後執⾏如下命令讓環境 ...
  • 學習Django有一段時間了,最近剛好寫了一個小項目,用到了前後端交互,剛開始寫前後端交互確實很讓人頭暈目眩呢,下麵我來給大家介紹三種簡單的Django前後端交互的方法吧! 第一種 通過form表單的get或post請求提交到後端的請求方式 <form> <input type='text' nam ...
  • 聲明區域: 變數等可以聲明的區域 例:全局變數的聲明區域為其聲明所在的文件 潛在作用域: 從聲明點開始,到其聲明域的結尾 作用域: 變數對程式而言可見的範圍(即除去潛在作用域中被局部變數等隱藏的區域) ...
  • Hi,大家好,我是明哥。 在自己學習 Golang 的這段時間里,我寫了詳細的學習筆記放在我的個人微信公眾號 《Go編程時光》,對於 Go 語言,我也算是個初學者,因此寫的東西應該會比較適合剛接觸的同學,如果你也是剛學習 Go 語言,不防關註一下,一起學習,一起成長。 我的線上博客:http://g ...
  • 我的LeetCode:https://leetcode cn.com/u/ituring/ 我的LeetCode刷題源碼[GitHub]:https://github.com/izhoujie/Algorithmcii LeetCode 5. 最長迴文子串 題目 給定一個字元串 s,找到 s 中最長 ...
一周排行
  • 一:背景 1. 講故事 曾今在項目中發現有同事自定義結構體的時候,居然沒有重寫Equals方法,比如下麵這段代碼: static void Main(string[] args) { var list = Enumerable.Range(0, 1000).Select(m => new Point ...
  • 最近一個朋友有個關於素數的小東西要寫一下,素數是什麼呢?除了1和他本身不能被其他數整除,那麼這個數就是素數,1除外哦。我們知道概念那就很簡單了,直接代碼擼起。 ...
  • 前言 在開發編程中,我們經常會遇到功能非常相似的功能模塊,只是他們的處理的數據不一樣,所以我們會分別採用多個方法來處理不同的數據類型。但是這個時候,我們就會想一個問題,有沒有辦法實現利用同一個方法來傳遞不同種類型的參數呢? 這個時候,泛型也就因運而生,專門來解決這個問題的。 泛型是在C 2.0就推出 ...
  • 本文章主要用於介紹在Asp.Net Mvc(C#)中使用Fleck製作一個Html5的即時聊天室,含有完整代碼和演示Demo。 ...
  • 出庫單的功能。能學習了出庫單管理之後,WMS的 主體功能算是完成了。當然一個成熟的WMS還包括了盤點,報表,策略規則,移庫功能及與其他系統(ERP、TMS等)的介面,實現無縫集成,打破信息孤島,讓數據實時、準確和同步。 ...
  • Data StructureThere're two types of variables in C#, reference type and value type.Enum:enum Color{Red=0,Green=1}//equals to enum Color{Red,//start fr... ...
  • 0. 前言 該項目使用Maven進行管理和構建,所以需要預先配置好Maven。嗯,在這個系列里就不做過多的介紹了。 1. 創建項目 先創建一個pom.xml 文件,添加以下內容: <?xml version="1.0" encoding="UTF-8"?> <project xmlns="http: ...
  • API 概述 API(Application Programming Interface),應用程式編程介面。 Java API是一本程式員的 字典 ,是JDK中提供給我們使用的類的說明文檔。 這些類將底層的代碼實現封裝了起來,我們不需要關心這些類是如何實現的,只需要學習這些類如何使用即可。 所以我 ...
  • 女程式員是這麼徵婚的: SELECT * FROM 男人們 WHERE 未婚=true and 同性戀=false and 有房=true and 有車=true and 條件 in (帥氣,紳士,大度,氣質,智慧,溫柔,體貼,會浪漫,活潑,可愛,最好還能帶孩子) and 年齡 between(24 ...
  • 有很多剛學習軟體測試的小伙伴,都會在網路上找尋各種學習資料,去提升自己的專業技能水平。因此,我決定定期分享我整理收集的一些軟體測試的測試工具下載、面試寶典、視頻教學合集。都整理好了,有需要的可以關註我(獲取方式在文末) 軟體測試的學習,不止是基礎理論,還需要學習測試工具的用法,如介面工具Postma ...