(｡･∀･)ﾉﾞ
嗨，我是wec，今天是Day 5。

🔎 題目難度與描述

難度：EASY

題目描述：

給定一個單向鏈結串列的首節點，反轉該串列，並返回反轉後的串列。

🔎 解題思路＆程式碼

1️⃣ 迭代法

第1步： 使用prev（前一節點）、curr（正在處理的節點）與next（暫存下一個要處理的節點）三個指針幫助串列進行反轉。
第2步： 將curr的下一個節點用next暫存，再把curr.next指向prev然後把prev和curr都向前移動一個節點（prev變curr，curr變next），重複以上動作直到curr不為null。
程式碼：

class ListNode
  attr_accessor :val, :next

  def initialize(val = 0, _next = nil)
    @val = val
    @next = _next
  end
end

def reverse_list(head)
  prev = nil
  curr = head

  while curr
    curr.next, prev, curr = prev, curr, curr.next
  end

  prev
end

2️⃣ 遞迴法

第1步： 把串列中除了首結點之外的其餘節點都反轉，如果串列中只有一個節點，則無須翻轉。
第2步： 將反轉後的串列的首節點保存，再將當前節點head的下一個節點的next指向head本身。
第3步： 然後把當前節點的next設為null(新的尾節點)。
第4步： return反轉後的鏈結串列的首節點。
程式碼：

def reverse_list(head)
  return head if head.nil? || head.next.nil?

  new_head = reverse_list(head.next)
  head.next.next = head
  head.next = nil

  new_head  
end

🔎 總結

時間複雜度比較

迭代解法： 時間複雜度為O(n)
遞歸解法： 時間複雜度為O(n)
➡️ 登愣，時間複雜度一樣，不過迭代法僅用了幾個指針去做保存的動作空間複雜度是常數等級O(1)，但遞迴法在每次調用時都會但用堆疊間，若遇到最壞的情況則空間複雜度會的達到O(n)，遞迴的深度太深、串列長度比我的命還長的話，就會導致堆疊溢位（stack overflow）的局面。
所以如果追求空間與性能的話，迭代是比較好的方法。但如果代碼的整潔性是優先考量的話，遞迴也可以作為其中一個選項ヽ(･ω･｡)ﾉ。

那麼，以上就是今天的內容！

相信IT人動腦時都要吃點東西，所以今天邊寫邊吃小番茄。
明天要說：Ruby精選刷題！練等要先從easy開始IV(>∀･)⌒☆