import Foundation

class OneWayLinkedList: CustomStringConvertible {
    class Node {
        private(set) var next: Node?
        private(set) var value: Int

        init(_ value: Int, next: Node?) {
            self.value = value
            self.next = next
        }
    }

    var description: String {
        if self.head == nil { return "nil"}
        var str = ""
        var node = self.head
        while let n = node {
            str.append("\(n.value)")
            node = node?.next
            if let _ = node { str.append("->") }
        }
        return str
    }

    private(set) var head: Node?

    init(nodesCount: Int) {
        var nextNode: Node? = nil
        (0..<nodesCount).forEach {
            let node = Node(nodesCount - $0 - 1, next: nextNode)
            nextNode = node
        }
        self.head = nextNode
    }
}

class TwoWayLinkedList: CustomStringConvertible {
    class Node {
        var next: Node?
        var previous: Node?
        private(set) var value: Int
        init(_ value: Int) {
            self.value = value
        }
    }

    var description: String {
        if self.head == nil { return "nil"}
        var str = ""
        var node = self.head
        while let n = node {
            str.append("\(n.value)")
            node = node?.next
            if let _ = node {str.append("<->")}
        }
        return str
    }
    private(set) var head: Node?
    private(set) var tail: Node?

    func unshift(_ value: Int) {
        let node = Node(value)
        if self.tail == nil { self.tail = node}
        if let head = self.head {
            node.next = head
            head.previous = node
        }
        self.head = node
    }
}

func splitList(starting head: OneWayLinkedList.Node?) -> [TwoWayLinkedList] {
    var node = head
    let odd = TwoWayLinkedList()
    let even = TwoWayLinkedList()
    var isOdd = true
    while let n = node {
        isOdd ? odd.unshift(n.value) : even.unshift(n.value)
        node = n.next
        isOdd = !isOdd
    }

    return [odd, even]
}

//test

let oneWayList = OneWayLinkedList(nodesCount: 20)
let lists = splitList(starting: oneWayList.head)
print(oneWayList)
print("odd:  \(lists[0])")
print("even: \(lists[1])")