/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
        var list1 = list1
        var list2 = list2
        if list1 == nil { return list2 }
        if list2 == nil { return list1 }
        var head = ListNode()
        var curr = head
        while (list1 != nil || list2 != nil) {
            if (list1 != nil && list2 != nil) {
                if (list1!.val < list2!.val) {
                    curr.next = ListNode(list1!.val)
                    list1 = list1!.next
                } else {
                    curr.next = ListNode(list2!.val)
                    list2 = list2!.next
                }
            } else if (list1 != nil) {
                curr.next = ListNode(list1!.val)
                list1 = list1!.next
            } else {
                curr.next = ListNode(list2!.val)
                list2 = list2!.next
            }
            curr = curr.next ?? curr;
        }
        return head.next
    }
}