日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問(wèn)題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
LeetCode題解之兩個(gè)有序鏈表合并

前言

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來(lái)自于我們對(duì)這個(gè)行業(yè)的熱愛(ài)。我們立志把好的技術(shù)通過(guò)有效、簡(jiǎn)單的方式提供給客戶，將通過(guò)不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長(zhǎng)期合作伙伴，公司提供的服務(wù)項(xiàng)目有：空間域名、網(wǎng)站空間、營(yíng)銷軟件、網(wǎng)站建設(shè)、遼陽(yáng)網(wǎng)站維護(hù)、網(wǎng)站推廣。

關(guān)于鏈表，常見(jiàn)的算法問(wèn)題有以下幾種：

  • 單鏈表反轉(zhuǎn)
  • 兩個(gè)有序的鏈表合并
  • 刪除鏈表倒數(shù)第n個(gè)結(jié)點(diǎn)
  • 求鏈表的中間結(jié)點(diǎn)
  • 鏈表中環(huán)的檢測(cè)

之前我們說(shuō)過(guò)了第一個(gè)問(wèn)題——單鏈表反轉(zhuǎn)，今天說(shuō)說(shuō)第二個(gè)問(wèn)題：兩個(gè)有序的鏈表合并

題目：兩個(gè)有序的鏈表合并

輸入兩個(gè)遞增排序的鏈表，合并這兩個(gè)鏈表并使新鏈表中的節(jié)點(diǎn)仍然是遞增排序的。

示例1：

輸入：1->2->4, 1->3->4

輸出：1->1->2->3->4->4

限制：

0 <= 鏈表長(zhǎng)度 <= 1000

解法一

先分析題干：遞增，鏈表，合并

兩個(gè)遞增的鏈表，合并成一個(gè)遞增的鏈表。

那么我們很容易想到一個(gè)方法就是，兩個(gè)指針?lè)謩e遍歷兩個(gè)鏈表：

比如兩個(gè)鏈表是node1、node2，然后一個(gè)新鏈表node3作為輸出

  • node1.val< node2.val。那么就把node3指向node1，然后node1指針向下走一步，再和node2.val相比較。
  • node1.val> node2.val。那么就把node3指向node2，然后node2指針向下走一步，再和node1.val相比較。

什么時(shí)候結(jié)束呢?當(dāng)某個(gè)node.next為null的時(shí)候，就代表結(jié)束了。

比如node1遍歷結(jié)束，就把node3直接指向node2。

 
 
 
 
    
  
  
  
  
  1. public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 
    2.   
  
  
  
  2.  //創(chuàng)建要輸出的鏈表結(jié)點(diǎn)dum，和一個(gè)用于類指針操作的結(jié)點(diǎn)cur 
    3.   
  
  
  
  3.         ListNode dum = new ListNode(0); 
    4.   
  
  
  
  4.         ListNode cur = dum; 
    5.   
  
  
  
  5.         //結(jié)束條件是當(dāng)其中一個(gè)結(jié)點(diǎn)為空 
    6.   
  
  
  
  6.         while(l1 !=null && l2 != null){ 
    7.   
  
  
  
  7.          //當(dāng)鏈表1的結(jié)點(diǎn)小的時(shí)候，就把cur指向這個(gè)結(jié)點(diǎn)，并且鏈表1下移到下個(gè)結(jié)點(diǎn) 
    8.   
  
  
  
  8.             if(l1.val <= l2.val){ 
    9.   
  
  
  
  9.                 cur.next=l1; 
    10.   
  
  
  
  10.                 l1=l1.next; 
    11.   
  
  
  
  11.             }else { 
    12.   
  
  
  
  12.                 cur.next=l2; 
    13.   
  
  
  
  13.                 l2=l2.next; 
    14.   
  
  
  
  14.             } 
    15.   
  
  
  
  15.             cur=cur.next; 
    16.   
  
  
  
  16.         } 
    17.   
  
  
  
  17.         cur.next = (l1 == null? l2 : l1); 
    18.   
  
  
  
  18.         return dum.next; 
    19.   
  
  
  
  19.     }     
    20.

時(shí)間復(fù)雜度

這個(gè)算法要遍歷兩個(gè)不同長(zhǎng)度的鏈表，所以時(shí)間復(fù)雜度為O(m+n)

空間復(fù)雜度

關(guān)于空間復(fù)雜度，有可能有的朋友會(huì)覺(jué)得用到了m+n長(zhǎng)度的鏈表?所以空間復(fù)雜度也是O(m+n)?

其實(shí)不然，鏈表并不會(huì)單獨(dú)創(chuàng)建額外的空間，我們其實(shí)只是新建了一個(gè)結(jié)點(diǎn)，然后將這個(gè)結(jié)點(diǎn)指向之前已經(jīng)有的結(jié)點(diǎn)空間地址，所以并沒(méi)有占用額外的m或者n大小的空間，只用到了dum和cur兩個(gè)結(jié)點(diǎn)的引用。

所以該解法的空間復(fù)雜度為O(1)

解法二

按照之前的格式，我們肯定會(huì)有第二種解法。

所以、我們需要想想，剛才的解法還有優(yōu)化點(diǎn)嗎?

是否可以不單獨(dú)創(chuàng)建鏈表結(jié)點(diǎn)呢?

其實(shí)可以發(fā)現(xiàn)我們每次操作都是類似的，都是比較大小，然后指定next結(jié)點(diǎn)。

所以我們可以寫成遞歸的寫法。

這里說(shuō)下遞歸的兩個(gè)要素：

1、找到每一次遞歸過(guò)程中需要的操作。也就是我們剛才說(shuō)的重復(fù)操作。

2、找到遞歸終止的條件。

那按照這個(gè)思路，我們就可以想想了：

  • 首先，是每一次遞歸過(guò)程中需要做的操作，寫段偽代碼：
 
 
 
 
    
  
  
  
  
  1. if (l1.val  
  
  
  
  2.  l1.next; 
    3.   
  
  
  
  3.  return l1; 
    4.   
  
  
  
  4. }else { 
    5.   
  
  
  
  5.  l2.next; 
    6.   
  
  
  
  6.  return l2; 
    7.   
  
  
  
  7. } 
    8.
  • 其次，我們要找到終止條件，也就是我們?cè)诮夥ㄒ恢蓄愃频臈l件，當(dāng)某個(gè)鏈表便利結(jié)束，結(jié)點(diǎn)為空的時(shí)候。
 
 
 
 
    
  
  
  
  
  1. if (l1 == null ) { 
    2.   
  
  
  
  2.  return l2; 
    3.   
  
  
  
  3. } 
    4.   
  
  
  
  4. if (l2 == null ) { 
    5.   
  
  
  
  5.  return l1; 
    6.   
  
  
  
  6. } 
    7.

那么結(jié)合這兩個(gè)遞歸要素，我們就可以寫出一個(gè)遞歸解法：

 
 
 
 
    
  
  
  
  
  1. public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 
    2.   
  
  
  
  2.         if(l1 == null || l2 == null) 
    3.   
  
  
  
  3.             return l1 == null ? l2 : l1; 
    4.   
  
  
  
  4.  
    5.   
  
  
  
  5.         if(l1.val  
  
  
  
  6.         { 
    7.   
  
  
  
  7.             l1.next = mergeTwoLists(l1.next, l2); 
    8.   
  
  
  
  8.             return l1; 
    9.   
  
  
  
  9.         } 
    10.   
  
  
  
  10.         else 
    11.   
  
  
  
  11.         { 
    12.   
  
  
  
  12.             l2.next = mergeTwoLists(l1, l2.next); 
    13.   
  
  
  
  13.             return l2; 
    14.   
  
  
  
  14.         } 
    15.   
  
  
  
  15.              
    16.   
  
  
  
  16.     } 
    17.

還是很奇妙的吧～都沒(méi)有用到單獨(dú)的結(jié)點(diǎn)引用。

我們可以這樣理解，有點(diǎn)像我們直接操作現(xiàn)實(shí)中的兩個(gè)鏈表，去給他們按順序進(jìn)行了一個(gè)連線：

時(shí)間復(fù)雜度

時(shí)間復(fù)雜度還是會(huì)走完兩個(gè)鏈表的每一個(gè)結(jié)點(diǎn)，所以還是O(m+n)

空間復(fù)雜度

都沒(méi)有用到單獨(dú)的空間，所以空間復(fù)雜度也是O(1)

參考

https://time.geekbang.org/column/article/41149

https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/

本文轉(zhuǎn)載自微信公眾號(hào)「碼上積木」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系碼上積木公眾號(hào)。


網(wǎng)站欄目：LeetCode題解之兩個(gè)有序鏈表合并
網(wǎng)頁(yè)地址：http://www.5511xx.com/article/dpspeoi.html