class Node<T: Equatable> {
    let value: T
    var next: Node<T>?
    
    init(_ value: T, next: Node<T>? = nil) {
        self.value = value
        self.next = next
    }
}

extension Node: CustomStringConvertible {
    var description: String { "\(value)" }
}

class LinkedList<T: Equatable> {
    var root: Node<T>?
    var last: Node<T>?
    
    init(root: Node<T>? = nil) {
        self.root = root
        self.last = root
    }
    
    func insert(_ node: Node<T>) {
        if root == nil {
            root = node
            last = node
        } else {
            last?.next = node
            last = node
        }
    }
    
    func delete(_ value: T) {
        let (previous, current) = _find(value)
        previous?.next = current?.next
    }
    
    private func _find(_ value: T) -> (previous: Node<T>?, node: Node<T>?) {
        var current: Node<T>? = root
        var previous: Node<T>? = nil
        
        while current != nil {
            if current?.value == value {
                break
            }
            
            previous = current
            current = current?.next
        }
        
        return (previous, current)
    }
    
    func find(_ value: T) -> Node<T>? {
        _find(value).node
    }
    
    func reverse() {
        var current: Node<T>? = root
        var previous: Node<T>? = nil
        var next: Node<T>? = nil
        
        while current != nil {
            next = current?.next
            current?.next = previous
            
            previous = current
            current = next
        }
        
        root = previous
    }
}

extension LinkedList: CustomStringConvertible {

    var description: String {
        guard let root else { return "" }
        
        var result = ""
        var current: Node<T>? = root
        
        while current != nil {
            result += "\(current!.value) -> "
            current = current?.next
        }
        
        return result + "nil"
    }
}

let list = LinkedList<Int>()
list.insert(Node(0))
list.insert(Node(1))
list.insert(Node(2))
list.insert(Node(3))
print(list)

print(list.find(2) ?? Node(-1))
list.delete(2)
print(list.find(2) ?? Node(-1))

print(list)
list.reverse()
print(list)