Перевернуть связанный список в Swift - PullRequest
Новая
       13

Перевернуть связанный список в Swift

0 голосов
/ 05 января 2019

Перевернуть связанный список в Swift легко. У меня есть рабочее решение. Однако при подготовке к собеседованиям на доске версия, которую я быстро создаю, просто не работает, и я не могу определить, почему.

Мне нужно знать, почему не работает следующее - с игровой площадки, я думаю, это потому, что 

tail = previous

Строковые ошибки и выполнение никогда не завершается. 

func reverseLL (node: Node?) -> Node? {
    guard node != nil else { return nil }
    var tail : Node? = node
    var previous = node?.next
    while previous != nil {
        let tailRef = previous?.next
        previous?.next = tail
        tail = previous
        previous = tailRef
    }
    return tail
    }

Мое определение связанного списка: 

class Node: CustomStringConvertible {
    var data: Int
    var next: Node?

    var description: String {
        return String(data) + (next != nil ? next!.description : "")
    }

    init (data: Int) {
        self.data = data
        next = nil
    }

    func appendToTail(data: Int) {
        if (next != nil) {
            next?.appendToTail(data: data)
        }
        else {
            next = Node(data: data)
        }
    }
}

Моя рабочая версия reverseLL (которую я принимаю как «Swifty») выглядит следующим образом, но я считаю, что она должна быть функционально идентична моему более раннему определению. 

 func reverseLL (node: Node?) -> Node? {
guard node != nil else { return nil }
        var tail: Node?
        var headNode = node
        while let head = headNode {
            let tailRef = head.next
            head.next = tail
            tail = head
            headNode = tailRef
        }
        return tail
    }

Итак, создание связанного списка с 

let ll = Node(data: 3)
ll.appendToTail(data: 4)
ll.appendToTail(data: 4)
ll.appendToTail(data: 5)

дает данные в порядке 3445

и обратно через 

reverseLL(node: ll)

дает данные в порядке 5443

Чтобы было понятно, почему 

tail = previous

выполнение остановки строки в моем первом определении reverseLL?

1 Ответ

0 голосов
/ 05 января 2019

Вторая версия более Swifty, так как вы используете необязательную привязку и избегаете ужасной принудительной распаковки.

Проблема в первой версии состоит в том, что tail изначально равен node. В приведенном вами примере это ( 3-> 4-> 4-> 5 ).

Поэтому, когда вы делаете previous?.next = tail в первой итерации, previous становится ( 4-> 4-> 5-> 3-> 4-> 5-> 3-> 4-> 5-> ... ). Обратите внимание, что узел с данными, равными 5, теперь указывает на узел с данными, равными 3. Что создает бесконечный цикл.

Облегчение

Охранное заявление также может быть записано как: 

guard node?.next != nil else {
    return node
}

, который будет включать списки с одним узлом.

...