日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

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

新聞中心

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

前言

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

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

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

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

題目：兩個有序的鏈表合并

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

示例1：

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

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

限制：

0 <= 鏈表長度 <= 1000

解法一

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

兩個遞增的鏈表，合并成一個遞增的鏈表。

那么我們很容易想到一個方法就是，兩個指針分別遍歷兩個鏈表：

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

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

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

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

 
 
 
 
    
  
  
  
  
  1. public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 
    2.   
  
  
  
  2.  //創(chuàng)建要輸出的鏈表結(jié)點(diǎn)dum，和一個用于類指針操作的結(jié)點(diǎn)cur 
    3.   
  
  
  
  3.         ListNode dum = new ListNode(0); 
    4.   
  
  
  
  4.         ListNode cur = dum; 
    5.   
  
  
  
  5.         //結(jié)束條件是當(dāng)其中一個結(jié)點(diǎn)為空 
    6.   
  
  
  
  6.         while(l1 !=null && l2 != null){ 
    7.   
  
  
  
  7.          //當(dāng)鏈表1的結(jié)點(diǎn)小的時候，就把cur指向這個結(jié)點(diǎn)，并且鏈表1下移到下個結(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.

時間復(fù)雜度

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

空間復(fù)雜度

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

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

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

解法二

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

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

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

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

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

這里說下遞歸的兩個要素：

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

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

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

  • 首先，是每一次遞歸過程中需要做的操作，寫段偽代碼：
 
 
 
 
    
  
  
  
  
  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.
  • 其次，我們要找到終止條件，也就是我們在解法一中類似的條件，當(dāng)某個鏈表便利結(jié)束，結(jié)點(diǎn)為空的時候。
 
 
 
 
    
  
  
  
  
  1. if (l1 == null ) { 
    2.   
  
  
  
  2.  return l2; 
    3.   
  
  
  
  3. } 
    4.   
  
  
  
  4. if (l2 == null ) { 
    5.   
  
  
  
  5.  return l1; 
    6.   
  
  
  
  6. } 
    7.

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

 
 
 
 
    
  
  
  
  
  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.

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

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

時間復(fù)雜度

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

空間復(fù)雜度

都沒有用到單獨(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)載自微信公眾號「碼上積木」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系碼上積木公眾號。


當(dāng)前文章：LeetCode題解之兩個有序鏈表合并
鏈接URL：http://www.dlmjj.cn/article/dpspeoi.html