21. 合并两个有序链表

解法一：递归

思路：很好理解，每次判断两个节点大小，要求是升序，所以小的返回。

class Solution {
    fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {
        l1 ?: return l2
        l2 ?: return l1

        return if (l1.`val` < l2.`val`) {
            l1.next = mergeTwoLists(l1.next, l2)
            l1
        } else {
            l2.next = mergeTwoLists(l1, l2.next)
            l2
        }
    }
}

解法二：迭代

思路：有递归就有迭代，道理是一样的。

class Solution {
    fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {

        val dummy = ListNode(-1)
        var cur = dummy

        var l1 = l1
        var l2 = l2

        while (l1 != null && l2 != null) {
            if (l1.`val` < l2.`val`) {
                cur.next = l1
                l1 = l1.next
            } else {
                cur.next = l2
                l2 = l2.next
            }
            cur = cur.next!!
        }
        if (l1 == null) cur.next = l2
        else if (l2 == null) cur.next = l1

        return dummy.next
    }
}

这题很简单啦~ ，但面试手写的话，我肯定直接写不出来，哈哈哈