https://leetcode-cn.com/problems/merge-two-sorted-lists/
//合并2个有序链表
object Solution {
    /**
    * 暴力遍历，时间复杂度O(M+N),空间复杂度O(1)
    */
    def mergeTwoLists(l1: ListNode, l2: ListNode): ListNode = {
        val prevHead = new ListNode(-1)
        var prev = prevHead
        var l1_cp= l1
        var l2_cp = l2
        while(l1_cp != null && l2_cp != null){
            if(l1_cp.x <= l2_cp.x){
                prev.next = l1_cp
                l1_cp = l1_cp.next 
            }else{
                prev.next = l2_cp
                l2_cp = l2_cp.next
            }
            prev = prev.next
        }
        if(l1_cp == null) prev.next = l2_cp else prev.next = l1_cp
        prevHead.next
    }
}