Pythonで解いたLeetCodeの問題をSwiftで解いてみよう「141. Linked List Cycle」

概要

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

問題

141. Linked List Cycle

LinkedList(連結リスト)が循環する構造ならTrue,ないならFalseを返してね、という問題

Pythonで実装

2つの方法で解いた。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        seen = set()
        while head != None:
            if head in seen:
                return True
            seen.add(head)
            head = head.next
        return False
# Runtime Details 62ms Beats 29.69%of users with Python3
# Memory Details 20.78MB Beats 12.82%of users with Python3

まずは単純なset()を用いた解き方。説明文の

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer.

箇所から分かるように、LinkedListの中にサイクルがあるということは、過去に出てきた要素が再びheadに入ってくるので、headの情報をsetの中に保存し、あとはひたすらhead.nextを続けてあげる。

そうすることで、もしサイクルがある場合にはsetに保存されている情報と同様の内容が再びheadとして回ってくることになる。
もしheadがNoneになればそれはサイクルが存在しないのでFalseを返す。

こちらの解法は単純で実装しやすいが、空間計算量がO(n)になるという欠点がある。
計算量はO(n)。

そこで二つ目の解法。
フロイドの循環検出法(ウサギと亀のアルゴリズム)を使っていて、こちらも比較的直感的に書ける。
※ざっくり説明すると、速いポインタと遅いポインタの二つを用いて数列や単方向のLinkedListに循環があるかを特定するアルゴリズム。SolutionsではTwo Poninterと書かれていることが多い。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if head is None:
            return False

        toroise = head
        hare =  head.next

        while toroise != hare:
            if hare is None or hare.next is None:
                return False
            toroise = toroise.next
            hare = hare.next.next
        return True
# Runtime Details 60ms Beats 43.40% of users with Python3
# Memory Details 20.12MB Beats 93.98%of users with Python3

こちらは計算量は最初の解法と同様にO(n)だが、空間計算量がO(1)と定数になるのが大きい。

Swiftで実装

上記と同様の内容をSwiftで書き直してみる。
例えば一つ目のSetを使った解法だが、

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */
class Solution {
    func hasCycle(_ head: ListNode?) -> Bool {
        var seen: Set<ListNode> = Set()

        var currentNode = head
        while currentNode != nil {
            if seen.contains(currentNode) {
                return true
            }
            seen.insert(currentNode)
            currentNode = currentNode?.next
        }
        return false
    }
}

Line 15: Char 25: error: type 'ListNode' does not conform to protocol 'Hashable' in solution.swift

そもそもListNodeがHashableに準拠していないため、この書き方はできない。

一応、ListNode型の変数を用意して以下のような書き方もできるが、遅い。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */

class Solution {
    func hasCycle(_ head: ListNode?) -> Bool {
        var nodesSeen:[ListNode] = [ListNode]()
        var currentNode = head

        while currentNode != nil {
            if nodesSeen.contains(where: { $0 === currentNode }) {
                return true
            }
            nodesSeen.append(currentNode!)
            currentNode = currentNode?.next
        }
        return false
    }
}
# Runtime Details 122ms Beats 5.23%of users with Swift
# Memory Details 16.07MB Beats 6.65%of users with Swift

これでは正直微妙なので、二つ目の解法を使用して書いてみることに。

class Solution {
    func hasCycle(_ head: ListNode?) -> Bool {
        if head == nil{
            return false
        }
        var tortoise = head
        var hare = head!.next

        while tortoise != hare {
            if hare == nil || hare?.next == nil {
                return false
            }
            tortoise = tortoise?.next
            hare = hare?.next?.next
        }
        return true
    }
}

サクッと書いて、Runしてみる。

Line 21: Char 24: error: operator function '!=' requires that 'ListNode' conform to 'Equatable' in solution.swift
while tortoise != hare {

・・・あれ？
となったが、そもそもSwiftではListNodeにはEquatableに準拠していない。
Equatableつけていない場合、hare,tortoiseのように変数を代入したときにこのような比較の仕方はできない。

なので、以下のように参照の不等号比較を行うことで無事通るようになる。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */

class Solution {
    func hasCycle(_ head: ListNode?) -> Bool {
        if head == nil{
            return false
        }
        var tortoise = head
        var hare = head!.next

        while tortoise !== hare {
            if hare == nil || hare?.next == nil {
                return false
            }
            tortoise = tortoise?.next
            hare = hare?.next?.next
        }
        return true
    }
}
# Runtime Details 49ms Beats 82.55%of users with Swift
# Memory　Details　15.70MB　Beats 52.02%of users with Swift

Swiftを使い始めたばかりで、Pythonのように思いついた解き方をスラスラと書けないもどかしさがある一方でやはり新しい言語の仕様を勉強する楽しさもあるので、今後も暇があれば書いていきたい。