概要

ゼロから始めるLeetCodeの時に解いた問題とかをSwiftで書いてみることにした。
シリーズ化するかは不明。

問題

206. Reverse Linked List

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くらいの記事を書きたいところ。