av激情亚洲男人的天堂国语,日韩欧美精品一中文字幕,无码av一区二区三区无码,国产又色又爽又刺激的a片,国产又色又爽又刺激的a片

LeetCode題解之兩個有序鏈表合并

前言

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

關于鏈表，常見的算法問題有以下幾種：

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

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

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

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

示例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相比較。

什么時候結束呢?當某個node.next為null的時候，就代表結束了。

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

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

時間復雜度

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

空間復雜度

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

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

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

解法二

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

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

是否可以不單獨創(chuàng)建鏈表結點呢?

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

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

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

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

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.
  • 其次，我們要找到終止條件，也就是我們在解法一中類似的條件，當某個鏈表便利結束，結點為空的時候。
 
 
 
 
    
  
  
  
  
  1. if (l1 == null ) { 
    2.   
  
  
  
  2.  return l2; 
    3.   
  
  
  
  3. } 
    4.   
  
  
  
  4. if (l2 == null ) { 
    5.   
  
  
  
  5.  return l1; 
    6.   
  
  
  
  6. } 
    7.

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

 
 
 
 
    
  
  
  
  
  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.

還是很奇妙的吧～都沒有用到單獨的結點引用。

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

時間復雜度

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

空間復雜度

都沒有用到單獨的空間，所以空間復雜度也是O(1)

參考

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

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

本文轉載自微信公眾號「碼上積木」，可以通過以下二維碼關注。轉載本文請聯(lián)系碼上積木公眾號。


本文題目：LeetCode題解之兩個有序鏈表合并
網(wǎng)頁鏈接：http://uogjgqi.cn/article/dpspeoi.html
掃二維碼與項目經(jīng)理溝通

我們在微信上24小時期待你的聲音

解答本文疑問/技術咨詢/運營咨詢/技術建議/互聯(lián)網(wǎng)交流