问题

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例

输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

解法一

看到这个题目，最直观的是什么？排序嘛，对不，我们将链表转化为数组，直接排序，最后组装一个新的链表，完事，因为两个链表本身 就是有序的，所以转化后的数组就是有序的，我们只需要依次比较两个数组，如下图：

type ListNode struct {
     Val int
     Next *ListNode
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    //声明三个切片
    slice1 := make([]int,0)
    slice2 := make([]int,0)
    slice3 := make([]int,0)
    //将链表转换为数组
    for l1 != nil{
        slice1 = append(slice1,l1.Val)
        l1 = l1.Next
    }
    for l2 != nil{
        slice2 = append(slice2,l2.Val)
        l2 = l2.Next
    }
    //开始依次比较，这里一定注意切片越界
    i,j := 0,0
    for i<len(slice1) && j <len(slice2){
        if slice1[i] <= slice2[j] {
            slice3 = append(slice3,slice1[i])
            i++
        }else{
            slice3 =append(slice3,slice2[j])
            j++
        }
    }
    //将切片剩余的值补充上去后面
    for i<len(slice1){
        slice3 = append(slice3,slice1[i])
        i++
    }
    for j<len(slice2){
        slice3 = append(slice3,slice2[j])
        j++
    }
    //将最终排好序的数组转换为链表进行返回
    var head,result  *ListNode = nil,nil
    for _,v := range slice3{
        if head  == nil{
            head = &ListNode{v,nil}
            result = head
            continue
        }
        head.Next = &ListNode{v,nil}
        head = head.Next
    }
    return result
}

上面代码我们可以看出申请了三个切片空间，其空间复杂度为O(n),在链表长度比较大的情况下，占用的额外空间回比较大，那怎么优化呢？

解法二

上面的解法一，我们申请了存放链表元素的数组空间，空间复杂度是O(n)，那么不转数组行不？O(1)的空间复杂度可以完成吗，能不转数组吗？直接根据链表来比较，这样就不要用消耗内存空间了，我们一起尝试一下？如下图

type ListNode struct {
     Val int
     Next *ListNode
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    //如果l1是nil,直接返回l2，因为链表本身是有序的
    if l1 == nil{
        return l2
    }
    //如果l2是nil,直接返回l2，因为链表本身是有序的
    if l2  == nil{
        return l1
    }
   //声明两个指针变量
    temp := &ListNode{-1,nil}
    result := temp
    for l1 != nil && l2 != nil{
        if l1.Val < l2.Val{ // l1链接
            n1 := l1
            temp.Next = n1
            temp = temp.Next
            l1 = l1.Next
        }else{ // l2链接
            n2 := l2
            temp.Next = n2
            temp = temp.Next
            l2 = l2.Next
        } 
    }
     //补全剩余的链表
    if l1 == nil {
        temp.Next = l2
    }
    if l2 == nil {
        temp.Next = l1
    }
    return result.Next
}

解法三

递归法,代码简单,感兴趣的了解一下,理解为最终要合并的两个链表长度一个为1，一个为0，满足递归终止条件。

type ListNode struct {
     Val int
     Next *ListNode
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    //如果l1是nil,直接返回l2，因为链表本身是有序的
    if l1 == nil{
        return l2
    }
    //如果l2是nil,直接返回l2，因为链表本身是有序的
    if l2  == nil{
        return l1
    }
   if l1.Val < l2.Val{
        //将l1的next节点指向为l2，也就是将大的挂在小的后面
        l1.Next = mergeTwoLists(l1.Next,l2)
        return l1
    }else{
        //将l2的next节点指向为l1，也就是将大的挂在小的后面
        l2.Next = mergeTwoLists(l2.Next,l1)
        return l2
    } 
}

欢迎大家关注微信公众号：“golang那点事”，更多精彩期待你的到来