溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶(hù)服務(wù)條款》

?LeetCode如何解決兩兩交換鏈表中的節(jié)點(diǎn)問(wèn)題

發(fā)布時(shí)間：2021-12-15 11:21:41 來(lái)源：億速云 閱讀：124 作者：小新 欄目：大數(shù)據(jù)

小編給大家分享一下LeetCode如何解決兩兩交換鏈表中的節(jié)點(diǎn)問(wèn)題，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！


題意


給定一個(gè)鏈表，兩兩交換其中相鄰的節(jié)點(diǎn)，并返回交換后的鏈表。
你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換。

 

樣例


 

     
給定   
      
      1->2->3->4  
      
      , 你應(yīng)該返回   
      
      2->1->4->3  
      
      .  
 

題解

遞歸法：  

  • 從鏈表的頭節(jié)點(diǎn) head 開(kāi)始遞歸。

  • 每次遞歸都負(fù)責(zé)交換一對(duì)節(jié)點(diǎn)。由 firstNode 和 secondNode 表示要交換的兩個(gè)節(jié)點(diǎn)。

  • 下一次遞歸則是傳遞的是下一對(duì)需要交換的節(jié)點(diǎn)。若鏈表中還有節(jié)點(diǎn)，則繼續(xù)遞歸。

  • 交換了兩個(gè)節(jié)點(diǎn)以后，返回 secondNode，因?yàn)樗墙粨Q后的新頭。

  • 在所有節(jié)點(diǎn)交換完成以后，我們返回交換后的頭，實(shí)際上是原始鏈表的第二個(gè)節(jié)點(diǎn)。


 
     
    
class  
      
      
      Solution { 
      
      
      
     
      
      
      public ListNode swapPairs(ListNode head) { 
      
      
      

 
      
      
      
         
      
      
      // If the list has no node or has only one node left.
 
      
      
      
         
      
      
      if ((head == 
 
      
      
      null) || (head.next == 
 
      
      
      null)) { 
      
      
      
             
      
      
      return head; 
      
      
      
        } 
      
      
      

 
      
      
      
         
      
      
      // Nodes to be swapped
 
      
      
      
        ListNode firstNode = head; 
      
      
      
        ListNode secondNode = head.next; 
      
      
      

 
      
      
      
         
      
      
      // Swapping
 
      
      
      
        firstNode.next = swapPairs(secondNode.next); 
      
      
      
        secondNode.next = firstNode; 
      
      
      

 
      
      
      
         
      
      
      // Now the head is the second node
 
      
      
      
         
      
      
      return secondNode; 
      
      
      
    } 
      
      
      
} 
      
      
       
     
    
 
時(shí)間復(fù)雜度：O(N)，其中       NN 指的是鏈表的節(jié)點(diǎn)數(shù)量。   空間復(fù)雜度：O(N)   ，遞歸過(guò)程使用的堆棧空間。  

以上是“LeetCode如何解決兩兩交換鏈表中的節(jié)點(diǎn)問(wèn)題”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！

向AI問(wèn)一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手