// MARK: - Смержить 2 linked lists

public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init() { self.val = 0; self.next = nil; }
    public init(_ val: Int) { self.val = val; self.next = nil; }
    public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
}

func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    if l1 == nil || l2 == nil { return l1 == nil ? l2 : l1 }
    if l1!.val <= l2!.val {
        l1?.next = mergeTwoLists(l1?.next, l2)
        return l1
    } else {
        l2?.next = mergeTwoLists(l1, l2?.next)
        return l2
    }
}

// без рекурсии
func mergeTwoList1(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    guard l1 != nil else { return l2 }
    guard l2 != nil else { return l1 }

    let mockHead: ListNode? = ListNode(0, nil) //если придет нил, чтобы проект не упал
    var l1 = l1
    var l2 = l2
    var endSortedList: ListNode? = mockHead

    while l1 != nil && l2 != nil {
        if l1!.val <= l2!.val {
            endSortedList?.next = l1
            l1 = l1?.next
        } else {
            endSortedList?.next = l2
            l2 = l2?.next
        }
        endSortedList = endSortedList?.next
    }
    endSortedList?.next = (l1 == nil) ? l2 : l1
    return mockHead?.next
}



let thirdNode = ListNode(4, nil)
let secondNode = ListNode(3, thirdNode)
let firstNode = ListNode(1, secondNode)

let node3 = ListNode(6, nil)
let node2 = ListNode(5, node3)
let node1 = ListNode(2, node2)
let test1 = mergeTwoList1(firstNode, node1)