概要
ゼロから始めるLeetCodeの時に解いた問題とかをSwiftで書いてみることにした。
シリーズ化するかは不明。
問題
LinkedList(連結リスト)の順番をひっくり返してね、という問題。
Pythonで実装
2つの方法で解いた。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev = None
curr = head
while curr:
temp = curr.next
curr.next = prev
prev = curr
curr = temp
return prev
# Runtime Details 33ms Beats 95.68%of users with Python3
# Memory Details 17.78MB Beats 81.84%of users with Python3
まずはポインタを最初から最後まで付け替えていくという解法。
パッと聞かれた時に答えやすい。
計算量はO(n)でリストの長さに依存する。空間計算量はO(1)。
そこで二つ目の解法。
スタックを使っていて、こちらも比較的直感的に書ける、が個人的には書く量が少し増えるのと、似たような処理を繰り返していてイマイチ感がある。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return head
stack = []
curr = head
while curr is not None:
stack.append(curr.val)
curr = curr.next
curr = head
while curr is not None:
curr.val = stack.pop()
curr = curr.next
return head
# Runtime Details 46ms Beats 30.26%of users with Python3
# Memory Details 17.78MB Beats 81.84%of users with Python3
こちらの計算量はO(n)、空間計算量がO(n)となる。
Swiftで実装
上記と同様の内容をSwiftで書き直してみる。
例えば一つ目の順番にポインタを付け替えていく解法だが、
/**
* Definition for singly-linked list.
* public class ListNode {
* public var val: Int
* public var next: ListNode?
* public init() { self.val = 0; self.next = nil; }
* public init(_ val: Int) { self.val = val; self.next = nil; }
* public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
class Solution {
func reverseList(_ head: ListNode?) -> ListNode? {
var prev:ListNode? = nil
var curr:ListNode? = head
while curr != nil{
var temp = curr?.next
curr?.next = prev
prev = curr
curr = temp
}
return prev
}
}
// Runtime Details 9ms Beats 83.54%of users with Swift
// Memory Details 14.73MB Beats 61.10%of users with Swift
こんな感じで書ける。
そこまで形式も変わらないし、せいぜいオプショナル周りに気をつけるだけなので楽に書ける。
二つ目の解法はというと、
/**
* Definition for singly-linked list.
* public class ListNode {
* public var val: Int
* public var next: ListNode?
* public init() { self.val = 0; self.next = nil; }
* public init(_ val: Int) { self.val = val; self.next = nil; }
* public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
class Solution {
func reverseList(_ head: ListNode?) -> ListNode? {
if head == nil {
return head
}
var curr: ListNode? = head
var stack:[Int] = []
while curr != nil {
stack.append(curr!.val)
curr = curr?.next
}
curr = head
while let node = stack.popLast() {
curr?.val = node
curr = curr?.next
}
return head
}
}
// Runtime Details 14ms Beats 10.22% of users with Swift
// Memory Details 14.90MB Beats 38.65% of users with Swift
これもオプショナル周りに気をつける。
Swift スタック
みたいなワードで検索してもスタックについての記事が出てこなかったので、おそらく専用的なスタックはなさそう。
ただ、append
とpopLast
があれば何とかなるのでそれで書き直した感じ。
Swiftを使い始めたばかりだとスパッと書ける感触はないけど、nil周りの挙動はオプショナル型のおかげで開発的には楽なのが良いところっすね。
次は難易度がMediumくらいの記事を書きたいところ。