import Foundation
class Node{
    let data: String
    private var next: Node?

    init (data: String){
        self.data = data
    }
}

class LinkedList{
    var head: Node

    init (n: Node){
        head = n
    }

    func addNode(n: Node){
        addNodeH(n, next: head)
    }

    func addNodeH(n: Node, next: Node?){
        if next!.next == nil{
          next!.next = n
      } else {
        addNodeH(n, next: next!.next)
     }
    }


    func addNodeOrdered(n: Node){
        if head.data > n.data{
            n.next = head
            head = n
        } else{
            addNodeOrderedHelper(n, next: head)
        }
    }

    func addNodeOrderedHelper(n: Node, next: Node?){
        if next!.next == nil{
            next!.next = n
        } else if (n.data < next!.next!.data){
            n.next = next!.next
            next!.next = n
       }
        else{
            addNodeOrderedHelper(n, next: next!.next)
        }
    }

func printList()-> String{
    return printListHelper(head)
}

func printListHelper(n: Node?)-> String{

    if(n == nil){
        return ""
    } else {
        return n!.data + " " + printListHelper(n!.next)
    }
}
}

var ll = LinkedList(n: Node(data:"zz"))
ll.addNodeOrdered(Node (data: "zo"))
ll.addNodeOrdered(Node (data: "jock"))
ll.addNodeOrdered(Node (data: "abs"))
ll.addNodeOrdered(Node (data: "zo"))
ll.addNodeOrdered(Node (data: "jock"))
ll.addNodeOrdered(Node (data: "abs"))
ll.addNodeOrdered(Node (data: "zo"))
ll.addNodeOrdered(Node (data: "jock"))
ll.addNodeOrdered(Node (data: "abs"))
print(ll.printList())