iT邦幫忙

2021 iThome 鐵人賽

DAY 15
1
自我挑戰組

【帶你輕鬆入門演算法-Leetcode】系列 第 15

【第十五天 - Linked list 題目分析】

  • 分享至 

  • xImage
  •  

https://ithelp.ithome.com.tw/upload/images/20210915/201405922uQFGYrK0x.png

  • 昨天問到,若 input 為 [1,2,3] 那麼 output 為 [2,1,3] 還是 [1,3,2] ?

    • 答案是 [2,1,3],根據題目的需求,從頭開始讀兩個 Node,將此兩個 Node 做交換,再讀兩個Node,並做交換,以此類推
  • 我們使用 迭代/遞迴 來解這個題目

    迭代 Iteration

    • 我們在真正的 Linked list 前,做一個假的 node 作為開頭,稱為 dummy node,dummy node 後面接的資料,才是真正 input 傳進來的 head
    • 所以我們每次執行 while 迴圈都要先判斷, current 後面兩個資料是否都存在
      • 若都存在,我們就將第一個 Node 叫做 first,第二個 Node 叫做 second (這兩個點預計要做交換)
      1. first 即將變成第二個點( second ),所以 first 指向的地方,要變成原本 second 指向的位置
      2. second 即將變成第一個點( first ),所以 second 指向的地方,就會變成 first
      3. 然後將 current 指向交換後的第一個位置 ( second )
      4. 經過上面三個步驟,交換完成,所以 current 會跳到 first 的位置,等待下一次再交換

https://ithelp.ithome.com.tw/upload/images/20210915/2014059285L5NYhmCE.png

https://ithelp.ithome.com.tw/upload/images/20210915/20140592XPiHUGQbzM.png

https://ithelp.ithome.com.tw/upload/images/20210915/20140592rWNOhI3Sw5.png

  • python 實作迭代如下:
    class Solution:
        def swapPairs(self, head: ListNode) -> ListNode:
    #       先儲存一個
            dummy = ListNode(0)
            dummy.next = head
            current = dummy

            while current.next != None and current.next.next != None:
    #           first 跟 second 儲存準備交換的 Node
                first = current.next
                second = current.next.next
    #           先把 first Node 指向 second 的下一個Node
                first.next = second.next
    #           先把 second Node 指向 first 的下一個Node 
                second.next = first 
    #           先把 second Node 指向 即將變成第一個點的 second 的下一個Node 
                current.next = second        
    #           把 current 跳到 first 的位置
                current = first
            return dummy.next

遞迴 Recursive

  • 根據題目,假設給定一個 linked list:
    https://ithelp.ithome.com.tw/upload/images/20210915/201405921aZc7yl4JD.png

我們需要輸出兩兩交換位置後的 linked list:
https://ithelp.ithome.com.tw/upload/images/20210915/20140592F5gs2TvW6L.png

  • 透過觀察,我們可以發現這個問題可以遞迴分割成小問題:
    給定一個 node *n,*假設 n 的下下個 node 之後的答案我們都知道了,則我們只要將 nn 的下一個 node 交換位置,再接上後面的答案即可。
  • 也就是說長度為 6 的 list,我們只要知道後四個節點的答案,就可以得到全部的答案;而要知道後四個節點的答案,只需要先知道後兩個節點的答案,依此類推。
    https://ithelp.ithome.com.tw/upload/images/20210915/201405929i0kMm9bjF.png

利用此遞迴關係,我們不斷將問題化簡成較短的 list ,直到 list 長度為 0 或 1 時,我們終於可以知道答案:
https://ithelp.ithome.com.tw/upload/images/20210915/20140592gzIh9EalEy.png

  • 當 list 長度為 0,則答案為 None
  • 當 list 長度為 1,則答案就是當前這個節點。

綜合以上發現我們可以列出遞迴關係式。為了方便表示,此處用一般的 list 進行表示,並且以 node_i+1 表示 node_i 所指向的下一個節點:

https://ithelp.ithome.com.tw/upload/images/20210915/20140592y015kqaCNH.png

其中,前兩種 case 為終止條件,第三個 case 為遞迴關係。

有了遞迴關係式,我們便可以撰寫程式:

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
#       head 指向第一個位置,若為空,則回傳 None
				if head is None: return None

#       second 指向第二個位置,若為空,則回傳 None        
        second = head.next
        if second is None: return head

#       rest 指向剩下的位置 (就是第二個位置之後)
        rest = second.next
        
#       交換前 [head, second, rest...] -> 交換後 [second, head, rest...]
#       第二個指向第一個,第一個指向剩下的
        second.next = head
        head.next = self.swapPairs(rest)
        
        return second

上一篇
【第十四天 - Linked list介紹】
下一篇
【第十六天 - 動態規劃 介紹】
系列文
【帶你輕鬆入門演算法-Leetcode】30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言